Metrics

[Morwenn]

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:

• Total running rime
• Cycles per element
• Number of comparisons
• Number of projections
• Number of moves

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:

• metric<T, Tag> type, basically a tagged value wrapper
• metrics<Metrics...> type, mostly a tuple of metric
• Tags (hold the printable name)
• Pretty print for metric and metrics
• combine_metrics
• A few simple metrics and associated tags:
  • comparisons
  • projections
  • running_time
• Tests
• Documentation
• Mention with example + output in quickstart