Module percentile

Source
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§

cluster
Operations on crate::Clusters.
pivot_fn

Structs§

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.

Enums§

MeanValue
The result of a percentile (e.g. median) lookup.

Traits§

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.

Functions§

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.