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 |
#769 in Algorithms
65,301 downloads per month
Used in 52 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 k
th 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);