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.

Performance

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.