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::Cluster
s. - 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§
- Mean
Value - The result of a percentile (e.g. median) lookup.
Traits§
- Ordered
List Index - Trait to get the index of a sorted list. Implemented by
Fraction
,KthSmallest
, andKthLargest
. - Percentile
Resolve - 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 andpivot_fn::rand
(if thepercentile-rand
feature is enabled, elsepivot_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
invalues
. Uses the best method available (percentile_rand
if featurepercentile-rand
is enabled, elsepivot_fn::middle
) - percentile_
default_ pivot_ by - Same as
percentile_default_pivot
but with a custom comparator function. - percentile_
rand percentile-rand
- Convenience function for
percentile
withpivot_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.