Module percentile

Expand description

Percentile / median calculations.

O(n log n) naive_percentile (simple to understand)
probabilistic O(n) percentile (recommended, fastest, and also quite simple to understand)
deterministic O(n) median_of_medians (harder to understand, probably slower than the probabilistic version. However guarantees linear time, so useful in critical applications.)

You should probably use percentile_rand.

The linear time algoritms are implementations following this blogpost.

Modules§

Fraction: A simplified fraction. This is used to get a percentile from any function in this module.
KthLargest: Get the k-th largest value. Implements OrderedListIndex.
KthSmallest: Get the k-th smallest value. Implements OrderedListIndex.

OrderedListIndex: Trait to get the index of a sorted list. Implemented by Fraction, KthSmallest, and KthLargest.
PercentileResolve: Resolves the mean function to return a concrete value. Accessible through MeanValue::resolve.

median: Convenience function for percentile with the 50% mark as the target and pivot_fn::rand (if the percentile-rand feature is enabled, else pivot_fn::middle).
median_of_medians: Same result as percentile_rand but in deterministic linear time. But probabilistically way slower.
median_of_medians_by: Same as median_of_medians but with a custom comparator function.
naive_percentile: Percentile by sorting.
naive_percentile_by: Same as naive_percentile but with a custom comparator function.
percentile: quickselect algorithm
percentile_by: Same as percentile but with a custom comparator function.
percentile_default_pivot: Get the value at target in values. Uses the best method available (percentile_rand if feature percentile-rand is enabled, else pivot_fn::middle)
percentile_default_pivot_by: Same as percentile_default_pivot but with a custom comparator function.
percentile_randpercentile-rand: Convenience function for percentile with pivot_fn::rand.
split_include: Moves items in the slice and splits it so the first returned slice contains all elements where predicate is true. The second contains all other.