adqselect
A lightweight crate that brings to Rust an nth_element implementation that leverages Andrei Alexandrescu's adaptive quickselect algorithm. Also available on crates.io.
Installation
Be sure that your Cargo.toml looks somewhat like this:
[dependencies]
adqselect = "0.1.3"
Usage
Bring the crate into scope:
extern crate adqselect;
use adqselect::nth_element;
then simply call nth_element on a vector.
let mut v = vec![10, 7, 9, 7, 2, 8, 8, 1, 9, 4];
nth_element(&mut v, 3, &mut Ord::cmp);
assert_eq!(v[3], 7);
This implementation also handles generic data types as long as they satisfy the PartialEq and PartialOrd traits.
Implementation
Link to the original paper: Fast Deterministic Selection by Andrei Alexandrescu.
The algorithm is based on a refined version of Median of Medians and it guarantees linear deterministic time complexity.
Benchmarks
Here are some benchmarks against other crates: floydrivest, order-stat, kth and pdqselect.
Results
Violin Plot
This chart shows the relationship between function/parameter and iteration time. The thickness of the shaded
region indicates the probability that a measurement of the given function/parameter would take a particular
length of time.
Line Chart
This chart shows the mean measured time for each function as the input (or the size of the input) increases.
adqselect on 1.000 random unsigned integers
adqselect on 10.000 random unsigned integers
adqselect on 100.000 random unsigned integers
adqselect on 1.000.000 random unsigned integers
floydrivest on 1.000 random unsigned integers
floydrivest on 10.000 random unsigned integers
floydrivest on 100.000 random unsigned integers
floydrivest on 1.000.000 random unsigned integers
kth on 1.000 random unsigned integers
kth on 10.000 random unsigned integers
kth on 100.000 random unsigned integers
kth on 1.000.000 random unsigned integers
order_stat on 1.000 random unsigned integers
order_stat on 10.000 random unsigned integers
order_stat on 100.000 random unsigned integers
order_stat on 1.000.000 random unsigned integers
pdqselect on 1.000 random unsigned integers
pdqselect on 10.000 random unsigned integers
pdqselect on 100.000 random unsigned integers
pdqselect on 1.000.000 random unsigned integers
This report was generated by
Criterion.rs, a statistics-driven benchmarking
library in Rust.
