Home

Awesome

Build Status License

miniselect: Generic selection and partial ordering algorithms

miniselect is a C++ header-only library that contains various generic selection and partial sorting algorithms with the ease of use, testing, advice on usage and benchmarking.

Sorting is everywhere and there are many outstanding sorting algorithms that compete in speed, comparison count and cache friendliness. However, selection algorithms are always a bit outside of the competition scope, they are pretty important, for example, in databases ORDER BY LIMIT N is used extremely often which can benefit from more optimal selection and partial sorting algorithms. This library tries to solve this problem with Modern C++.

Table of Contents

Quick Start

You can either include this project as a cmake dependency and then use the headers that are provided in the include folder or just pass the include folder to your compiler.

#include <iostream>
#include <vector>

#include "miniselect/median_of_ninthers.h"

int main() {
  std::vector<int> v = {1, 8, 4, 3, 2, 9, 0, 7, 6, 5};
  miniselect::median_of_ninthers_select(v.begin(), v.begin() + 5, v.end());
  for (const int i : v) {
    std::cout << i << ' ';
  }
  return 0;
}
// Compile it `clang++/g++ -I$DIRECTORY/miniselect/include/ example.cpp -std=c++11 -O3 -o example
// Possible output: 0 1 4 3 2 5 8 7 6 9
//                            ^ on the right place

Examples can be found in examples.

We support all compilers starting from GCC 7 and Clang 6. We are also planning to support Windows, for now it is best effort but no issues are known so far.

More on which algorithms are available, see documentation. For overview of this work you can read the article in the author's blog.

Testing

To test and benchmark, we use Google benchmark library. Simply do in the root directory:

# Check out the libraries.
$ git clone https://github.com/google/benchmark.git
$ git clone https://github.com/google/googletest.git
$ mkdir build && cd build
$ cmake -DMINISELECT_TESTING=on -DBENCHMARK_ENABLE_GTEST_TESTS=off -DBENCHMARK_ENABLE_TESTING=off ..
$ make -j
$ ctest -j4 --output-on-failure

It will create two tests and two benchmarks test_sort, test_select, benchmark_sort, benchmark_select. Use them to validate or contribute. You can also use ctest.

Documentation

There are several selection algorithms available, further $n$ is the number of elements in the array, $k$ is the selection element that is needed to be found (all algorithms are deterministic and not stable unless otherwise is specified):

NameAverageBest CaseWorst CaseComparisonsMemory
pdqselect$O(n)$$O(n)$$O(n\log n)$At least $2n$. Random data $2.5n$$O(1)$
Floyd-Rivest$O(n)$$O(n)$$O(n^2)$Avg: $n + \min(k, n - k) + O(\sqrt{n \log n})$$O(\log\log n)$
Median Of Medians$O(n)$$O(n)$$O(n)$Between $2n$ and $22n$. Random data $2.5n$$O(\log n)$
Median Of Ninthers$O(n)$$O(n)$$O(n)$Between $2n$ and $21n$. Random data $2n$$O(\log n)$
Median Of 3 Random$O(n)$$O(n)$$O(n^2)$At least $2n$. Random data $3n$$O(\log n)$
HeapSelect$O(n\log k)$$O(n)$$O(n\log k)$$n\log k$ on average, for some data patterns might be better$O(1)$
libstdc++ (introselect)$O(n)$$O(n)$$O(n\log n)$At least $2n$. Random data $3n$$O(1)$
libc++ (median of 3)$O(n)$$O(n)$$O(n^2)$At least $2n$. Random data $3n$$O(1)$

For sorting the situation is similar except every line adds $O(k\log k)$ comparisons and pdqselect is using $O(\log n)$ memory.

API

All functions end either in select, either in partial_sort and their behavior is exactly the same as for std::nth_element and std::partial_sort respectively, i.e. they accept 3 arguments as first, middle, end iterators and an optional comparator. Several notes:

<p align="center"><img src="https://media.giphy.com/media/TXIm9rTmbmox5ceSyP/giphy.gif" /></p>

We present here two gifs, for median and for $k = n/10$ order statistic.

<p float="left"> <img src="https://media.giphy.com/media/a5ORb22iMCE0a6D2cf/giphy.gif" width="48%" /> <img src="https://media.giphy.com/media/Gpk4c9pHMJLbjugDmZ/giphy.gif" width="48%" /> </p> <p align="center"><img src="https://media.giphy.com/media/C0txh78ngyEGqmrX7c/giphy.gif" /></p> <p align="center"><img src="https://media.giphy.com/media/usKlqJoh1WVLWLU9Dt/giphy.gif" /></p> <p align="center"><img src="https://media.giphy.com/media/GrbIu6PvrMuvoowp3U/giphy.gif" /></p> <p align="center"><img src="https://media.giphy.com/media/VOBM4MVBpiTgkbA6CH/giphy.gif" /></p> <p align="center"><img src="https://media.giphy.com/media/03eJ0S7H79Jdtrv49F/giphy.gif" /></p> <p align="center"><img src="https://media.giphy.com/media/MAw3Tk2TDxrnv6vLlu/giphy.gif" /></p>

Other algorithms to come

Performance results

We use 10 datasets and 8 algorithms with 10000000 elements to find median and other $k$ on Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz for std::vector<int>, for median the benchmarks are the following:

median

median

median

For smaller $k$, for example, 1000, the results are the following

k equals 1000

k equals 1000

k equals 1000

Other benchmarks can be found here.

Real-world usage

If you are planning to use miniselect in your product, please work from one of our releases and if you wish, you can write the acknowledgment in this section for visibility.

Contributing

Patches are welcome with new algorithms! You should add the selection algorithm together with the partial sorting algorithm in include, add tests in testing and ideally run benchmarks to see how it performs. If you also have some data cases to test against, we would be more than happy to merge them.

Motivation

The author was surveying research on small $k$ in selection algorithms and was struggling to find working implementations to compare different approaches from standard library and quickselect algorithms. It turned out that the problem is much more interesting than it looks, and after consulting The Art of Computer Programming from Donald Knuth about minimum comparison sorting and selection algorithms, the author decided to look through unpopular algorithms and try them out. Not finding any satisfactory library for selection algorithms nor research corresponding to the open source codes, the author set out to write one generic library.

For a big story of adventures see the author's blog post.

License

The code is made available under the Boost License 1.0.

Third-Party Libraries Used and Adjusted

LibraryLicense
pdqsortMIT
MedianOfNinthersBoost License 1.0