search

Morwenn / cpp-sort

Sorting algorithms & related tools for C++14
MIT License
621 stars 57 forks source link

Metrics #214

Open Morwenn opened 1 year ago

Morwenn commented 1 year ago

Currently we've got measures of presortedness to analyze the collections to sort, but no module to analyze how sorters perform except for counting_adapter. Which is actually a shame since I am the first one to use such metrics when I need to show how much algorithms have improved in release notes. Historically I've used the following metrics to analyze algorithms:

The simplest design would be for metrics to be sorter adapters, with a twist allowing them to combine their results into some kind of generic tuple with tag-based accessors (the original Ranges TS had such an extension to tuple, I could look into that, it would be yet another partial solution to #134). Said tuple should be printable, in which case it would display the information it gathered.

All metrics would go in a cppsort::metric namespace, and the individual files would go in cpp-sort/adapters/metrics, with or without a metrics.h file allowing to include them all.

To make metrics more usable, a combine_metrics utility could be introduced, allowing to write something along these lines:

template<typename Sorter>
struct add_metrics_to: cppsort::combine_metrics<
    cppsort::metrics::comparisons,
    cppsort::metrics::projections,
    cppsort::metrics::moves
> { /* ... */ };

auto my_sort = add_metrics_to(cppsort::quick_sort);
auto metrics = my_sort(my_collection);
std::cout << metrics;

I believe that those metrics can mostly be implemented in a non-intrusive way, though the moves counter might be trickier to get right.

Roadmap for a first release - the helper types can be simple at first and completed later as needed: