3 releases
Uses old Rust 2015
| 0.1.3 | Apr 23, 2016 |
|---|---|
| 0.1.2 | Apr 26, 2015 |
| 0.1.1 |
|
| 0.1.0 | Apr 24, 2015 |
#873 in Algorithms
70,641 downloads per month
Used in 55 crates
(11 directly)
20KB
345 lines
order-stat
Compute order statistics and median-of-medians.
lib.rs:
Calculate order statistics.
This crates allows one to compute the kth smallest element in
(expected) linear time, and estimate a median element via the
median-of-medians algorithm.
Installation
Ensure your Cargo.toml contains:
[dependencies]
order-stat = "0.1"
Examples
The kth function allows computing order statistics of slices of
Ord types.
let mut v = [4, 1, 3, 2, 0];
println!("the 2nd smallest element is {}", // 1
order_stat::kth(&mut v, 1));
The kth_by function takes an arbitrary closure, designed for
order statistics of slices of floating point and more general
comparisons.
let mut v = [4.0, 1.0, 3.0, 2.0, 0.0];
println!("the 3rd smallest element is {}", // 2
order_stat::kth_by(&mut v, 2, |x, y| x.partial_cmp(y).unwrap()));
#[derive(Debug)]
struct Foo(i32);
let mut v = [Foo(4), Foo(1), Foo(3), Foo(2), Foo(0)];
println!("the element with the 4th smallest field is {:?}", // Foo(3)
order_stat::kth_by(&mut v, 3, |x, y| x.0.cmp(&y.0)));
The median_of_medians function gives an approximation to the
median of a slice of an Ord type.
let mut v = [4, 1, 3, 2, 0];
println!("{} is close to the median",
order_stat::median_of_medians(&mut v).1);
It also has a median_of_medians_by variant to work with
non-Ord types and more general comparisons.
let mut v = [4.0, 1.0, 3.0, 2.0, 0.0];
println!("{} is close to the median",
order_stat::median_of_medians_by(&mut v, |x, y| x.partial_cmp(y).unwrap()).1);
#[derive(Debug)]
struct Foo(i32);
let mut v = [Foo(4), Foo(1), Foo(3), Foo(2), Foo(0)];
println!("{:?}'s field is close to the median of the fields",
order_stat::median_of_medians_by(&mut v, |x, y| x.0.cmp(&y.0)).1);