adqselect
一个轻量级的crate，为Rust带来了一个利用Andrei Alexandrescu的nth_element实现，该实现利用了自适应快速选择算法。也可在crates.io上找到。
安装
确保你的Cargo.toml看起来像这样
[dependencies]
adqselect = "0.1.3"
使用
将crate引入作用域
extern crate adqselect;
use adqselect::nth_element;
然后在vector上简单地调用nth_element。
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);
此实现还处理满足PartialEq和PartialOrd特性的泛型数据类型。
实现
链接到Andrei Alexandrescu的原始论文：快速确定性选择。
该算法基于改进的Median of Medians版本，并保证线性确定性时间复杂度。
基准测试
以下是一些与其他crate的基准测试： floydrivest， order-stat， kth 和 pdqselect。
结果
小提琴图
此图表显示了函数/参数与迭代时间之间的关系。阴影区域的厚度表示给定函数/参数的测量值可能持续特定时间的概率。
折线图
此图表显示了随着输入（或输入大小）的增加，每个函数的平均测量时间。
adqselect在1.000个随机无符号整数上的结果
adqselect在10.000个随机无符号整数上的结果
adqselect在100.000个随机无符号整数上的结果
adqselect在1.000.000个随机无符号整数上的结果
floydrivest在1.000个随机无符号整数上的结果
floydrivest在10.000个随机无符号整数上的结果
floydrivest在100.000个随机无符号整数上的结果
floydrivest在1.000.000个随机无符号整数上的结果
kth在1.000个随机无符号整数上的结果
kth在10.000个随机无符号整数上的结果
kth在100.000个随机无符号整数上的结果
kth在1.000.000个随机无符号整数上的结果
order_stat在1.000个随机无符号整数上的结果
order_stat在10.000个随机无符号整数上的结果
order_stat在100.000个随机无符号整数上的结果
order_stat在1.000.000个随机无符号整数上的结果
pdqselect在1.000个随机无符号整数上的结果
pdqselect在10.000个随机无符号整数上的结果
在100,000个随机无符号整数上运行pdqselect
在1,000,000个随机无符号整数上运行pdqselect
