Module percentile

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.