#adaptive #SELECT #nth_element #quickselect #order_statistics

adqselect

A lightweight crate that brings an implementation of nth_element by using the adaptive quickselect algorithm by Andrei Alexandrescu

4 releases

0.1.3 Jan 10, 2021
0.1.2 Jan 10, 2021
0.1.1 Aug 13, 2020
0.1.0 Aug 13, 2020

#147 in Algorithms

MIT license

1.5MB
339 lines

adqselect

License: MIT frjnn codecov

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

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

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

PDF of Slope Regression

adqselect on 10.000 random unsigned integers

PDF of Slope Regression

adqselect on 100.000 random unsigned integers

PDF of Slope Regression

adqselect on 1.000.000 random unsigned integers

PDF of Slope Iteration Times

floydrivest on 1.000 random unsigned integers

PDF of Slope Regression

floydrivest on 10.000 random unsigned integers

PDF of Slope Regression

floydrivest on 100.000 random unsigned integers

PDF of Slope Regression

floydrivest on 1.000.000 random unsigned integers

PDF of Slope Iteration Times

kth on 1.000 random unsigned integers

PDF of Slope Regression

kth on 10.000 random unsigned integers

PDF of Slope Regression

kth on 100.000 random unsigned integers

PDF of Slope Regression

kth on 1.000.000 random unsigned integers

PDF of Slope Iteration Times

order_stat on 1.000 random unsigned integers

PDF of Slope Regression

order_stat on 10.000 random unsigned integers

PDF of Slope Regression

order_stat on 100.000 random unsigned integers

PDF of Slope Regression

order_stat on 1.000.000 random unsigned integers

PDF of Slope Iteration Times

pdqselect on 1.000 random unsigned integers

PDF of Slope Regression

pdqselect on 10.000 random unsigned integers

PDF of Slope Regression

pdqselect on 100.000 random unsigned integers

PDF of Slope Regression

pdqselect on 1.000.000 random unsigned integers

PDF of Slope Iteration Times

This report was generated by Criterion.rs, a statistics-driven benchmarking library in Rust.

No runtime deps