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).