Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Metrics #214

Open
4 of 12 tasks
Morwenn opened this issue Dec 11, 2022 · 0 comments
Open
4 of 12 tasks

Metrics #214

Morwenn opened this issue Dec 11, 2022 · 0 comments
Labels

Comments

@Morwenn
Copy link
Owner

Morwenn commented Dec 11, 2022

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
@Morwenn Morwenn added this to the 1.15.0 milestone Jan 15, 2023
@Morwenn Morwenn removed this from the 1.15.0 milestone Aug 7, 2023
Morwenn added a commit that referenced this issue Aug 27, 2023
Morwenn added a commit that referenced this issue Aug 28, 2023
Morwenn added a commit that referenced this issue Sep 6, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant