Skip to content

Rust nth_element implementation that leverages Andrei Alexandrescu's Adaptive Quickselect algorithm.

License

Notifications You must be signed in to change notification settings

frjnn/adqselect

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

About

Rust nth_element implementation that leverages Andrei Alexandrescu's Adaptive Quickselect algorithm.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages