#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum QuantileRule {
Linear,
#[cfg_attr(
not(test),
expect(
dead_code,
reason = "binning is the first consumer; it removes this attribute"
)
)]
AveragedInvertedCdf,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[cfg_attr(
not(test),
expect(
dead_code,
reason = "weighted binning is the first consumer; it removes this attribute"
)
)]
pub(crate) enum WeightedQuantileRule {
InvertedCdf,
AveragedInvertedCdf,
}
pub(crate) fn sort_for_quantiles(scratch: &mut [f64]) {
scratch.sort_unstable_by(f64::total_cmp);
}
#[cfg_attr(
not(test),
expect(
dead_code,
reason = "weighted binning is the first consumer; it removes this attribute"
)
)]
pub(crate) fn sort_weighted_for_quantiles(scratch: &mut [(f64, f64)]) {
scratch.sort_by(|left, right| left.0.total_cmp(&right.0));
}
pub(crate) fn quantile_sorted(sorted: &[f64], percentile: f64, rule: QuantileRule) -> f64 {
assert!(!sorted.is_empty(), "a quantile needs at least one value");
assert!(
(0.0..=100.0).contains(&percentile),
"percentile {percentile} is outside 0..=100"
);
debug_assert!(
sorted
.windows(2)
.all(|pair| pair[0].total_cmp(&pair[1]).is_le()),
"the sample is not ascending, so its order statistics are not its own"
);
match rule {
QuantileRule::Linear => linear(sorted, percentile),
QuantileRule::AveragedInvertedCdf => {
let count = sorted.len();
let (index, exact) = inverted_cdf_position(
(1..=count).map(|running| running as f64),
count,
(percentile / 100.0) * count as f64,
);
averaged(sorted, index, exact)
}
}
}
#[cfg_attr(
not(test),
expect(
dead_code,
reason = "weighted binning is the first consumer; it removes this attribute"
)
)]
pub(crate) fn weighted_quantile_sorted(
sorted: &[(f64, f64)],
percentile: f64,
rule: WeightedQuantileRule,
) -> f64 {
assert!(!sorted.is_empty(), "a quantile needs at least one value");
assert!(
(0.0..=100.0).contains(&percentile),
"percentile {percentile} is outside 0..=100"
);
debug_assert!(
sorted
.windows(2)
.all(|pair| pair[0].0.total_cmp(&pair[1].0).is_le()),
"the sample is not ascending, so its order statistics are not its own"
);
debug_assert!(
sorted.iter().all(|&(_, weight)| weight >= 0.0),
"a negative weight makes the running weight non-monotone, so \
'the first index reaching the target' stops being well defined"
);
let total = super::sum_in_order(sorted.iter().map(|&(_, weight)| weight));
assert!(
total > 0.0,
"the sample weights total {total}, so no percentile of it is defined"
);
let mut running = 0.0;
let (index, exact) = inverted_cdf_position(
sorted.iter().map(move |&(_, weight)| {
running += weight;
running
}),
sorted.len(),
(percentile / 100.0) * total,
);
let values = |position: usize| sorted[position].0;
match rule {
WeightedQuantileRule::InvertedCdf => values(index),
WeightedQuantileRule::AveragedInvertedCdf => {
if exact && index + 1 < sorted.len() {
(values(index) + values(index + 1)) / 2.0
} else {
values(index)
}
}
}
}
fn inverted_cdf_position(
cumulative: impl Iterator<Item = f64>,
count: usize,
target: f64,
) -> (usize, bool) {
let last = count - 1;
for (index, running) in cumulative.enumerate() {
if running >= target {
return (index, running == target);
}
if index == last {
return (last, false);
}
}
unreachable!("a non-empty sample yields at least one running weight")
}
fn averaged(sorted: &[f64], index: usize, exact: bool) -> f64 {
if exact && index + 1 < sorted.len() {
(sorted[index] + sorted[index + 1]) / 2.0
} else {
sorted[index]
}
}
fn linear(sorted: &[f64], percentile: f64) -> f64 {
let last = sorted.len() - 1;
let position = (percentile / 100.0) * last as f64;
let lower = position.floor();
let fraction = position - lower;
let index = lower as usize;
if index >= last {
return sorted[last];
}
sorted[index] + fraction * (sorted[index + 1] - sorted[index])
}
#[cfg(test)]
mod tests {
use super::*;
const DIVERGENT: [f64; 7] = [0.0, 10.0, 25.0, 50.0, 75.0, 90.0, 100.0];
fn linear_at(sample: &[f64], percentile: f64) -> f64 {
quantile_sorted(sample, percentile, QuantileRule::Linear)
}
#[test]
fn a_two_element_sample_interpolates_rather_than_picking_an_order_statistic() {
assert_eq!(linear_at(&[0.0, 1.0], 25.0), 0.25);
assert_eq!(linear_at(&[0.0, 1.0], 50.0), 0.5);
assert_eq!(linear_at(&[0.0, 1.0], 75.0), 0.75);
}
#[test]
fn the_four_element_reference_row_is_reproduced_bit_for_bit() {
let sample = [0.0, 1.0, 2.0, 10.0];
let expected: [f64; 7] = [
0.0,
0.300_000_000_000_000_04,
0.75,
1.5,
4.0,
7.600_000_000_000_001,
10.0,
];
for (percentile, expected) in DIVERGENT.iter().zip(expected) {
let actual = linear_at(&sample, *percentile);
assert_eq!(
actual.to_bits(),
expected.to_bits(),
"Q({percentile}) was {actual}, expected {expected}"
);
}
}
#[test]
fn the_robust_scaling_statistics_match_the_worked_examples() {
let rows: [(&[f64], f64, f64, f64); 3] = [
(&[0.0, 1.0], 0.25, 0.5, 0.75),
(&[0.0, 1.0, 10.0], 0.5, 1.0, 5.5),
(&[-3.0, 0.5, 2.0, 11.0], -0.375, 1.25, 4.25),
];
for (sample, lower, median, upper) in rows {
assert_eq!(linear_at(sample, 25.0), lower, "Q25 of {sample:?}");
assert_eq!(linear_at(sample, 50.0), median, "Q50 of {sample:?}");
assert_eq!(linear_at(sample, 75.0), upper, "Q75 of {sample:?}");
}
}
#[test]
fn a_single_value_is_every_percentile_of_itself() {
for percentile in DIVERGENT {
assert_eq!(linear_at(&[5.0], percentile), 5.0);
assert_eq!(
linear_at(&[-0.0], percentile).to_bits(),
(-0.0_f64).to_bits()
);
}
}
#[test]
fn the_endpoints_are_the_extrema_exactly() {
let samples: [&[f64]; 4] = [
&[5.0],
&[0.0, 1.0],
&[-3.0, 0.5, 2.0, 11.0],
&[1.0, 1.0, 1.0, 2.0, 900.0],
];
for sample in samples {
assert_eq!(linear_at(sample, 0.0), sample[0], "Q0 of {sample:?}");
assert_eq!(
linear_at(sample, 100.0),
sample[sample.len() - 1],
"Q100 of {sample:?}"
);
}
}
#[test]
fn repeated_values_collapse_the_interpolation_onto_themselves() {
let sample = [0.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 100.0];
assert_eq!(linear_at(&sample, 25.0), 5.0);
assert_eq!(linear_at(&sample, 50.0), 5.0);
assert_eq!(linear_at(&sample, 75.0), 5.0);
}
#[test]
fn quantiles_are_monotone_in_the_percentile() {
let sample = [-7.5, -0.25, 0.0, 0.0, 1.0, 3.5, 12.0, 900.0, 1e6];
let mut previous = f64::NEG_INFINITY;
let mut ascents = 0_usize;
for step in 0..=1_000 {
let percentile = f64::from(step) / 10.0;
let value = linear_at(&sample, percentile);
assert!(value >= previous, "Q({percentile}) = {value} fell back");
ascents += usize::from(previous.is_finite() && value > previous);
previous = value;
}
assert_eq!(
ascents, 875,
"the sweep rose at {ascents} of its 1000 steps; every step but the \
125 inside the tied bracket has to rise, so a constant or \
order-statistic result is short and an interpolation across the \
tie is long"
);
assert_eq!(linear_at(&sample, 0.0), sample[0], "the sweep starts low");
assert_eq!(previous, sample[sample.len() - 1], "and ends at the top");
}
mod preconditions {
use super::*;
#[test]
#[should_panic = "a quantile needs at least one value"]
fn an_empty_sample_fails_instead_of_wrapping_its_length() {
let _ = linear_at(&[], 50.0);
}
#[test]
#[should_panic = "percentile -10 is outside"]
fn a_percentile_below_the_range_fails_instead_of_returning_a_plausible_one() {
let _ = linear_at(&[0.0, 1.0, 2.0, 10.0], -10.0);
}
#[test]
#[should_panic = "percentile 110 is outside"]
fn a_percentile_above_the_range_fails_instead_of_saturating_onto_the_maximum() {
let _ = linear_at(&[0.0, 1.0, 2.0, 10.0], 110.0);
}
#[test]
#[should_panic = "percentile NaN is outside"]
fn a_nan_percentile_fails_instead_of_returning_nan() {
let _ = linear_at(&[0.0, 1.0, 2.0, 10.0], f64::NAN);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic = "not ascending"]
fn a_descending_sample_fails_in_a_debug_build() {
let _ = linear_at(&[1.0, 0.0], 50.0);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic = "not ascending"]
fn signed_zeros_out_of_total_order_fail_too() {
let _ = linear_at(&[0.0, -0.0], 50.0);
}
}
#[test]
fn sorting_is_what_makes_input_order_irrelevant() {
let unsorted = [11.0, -3.0, 2.0, 0.5];
let mut scratch = unsorted;
sort_for_quantiles(&mut scratch);
assert_eq!(scratch, [-3.0, 0.5, 2.0, 11.0]);
assert_eq!(linear_at(&scratch, 25.0), -0.375);
let mut other = [2.0, 11.0, 0.5, -3.0];
sort_for_quantiles(&mut other);
assert_eq!(other, scratch);
}
#[test]
fn sorting_orders_signed_zeros_and_leaves_no_pair_incomparable() {
let mut scratch = [0.0, -1.0, -0.0, 1.0];
sort_for_quantiles(&mut scratch);
assert_eq!(scratch, [-1.0, -0.0, 0.0, 1.0]);
assert!(scratch[1].is_sign_negative() && scratch[2].is_sign_positive());
}
mod step_rules {
use super::*;
fn averaged_at(sample: &[f64], percentile: f64) -> f64 {
quantile_sorted(sample, percentile, QuantileRule::AveragedInvertedCdf)
}
fn weighted_at(sample: &[(f64, f64)], percentile: f64, rule: WeightedQuantileRule) -> f64 {
weighted_quantile_sorted(sample, percentile, rule)
}
fn pairs(values: &[f64], weights: &[f64]) -> Vec<(f64, f64)> {
values
.iter()
.copied()
.zip(weights.iter().copied())
.collect()
}
#[test]
fn the_worked_example_reproduces_all_four_cells() {
let values = [1.0, 2.0, 3.0, 10.0];
let unit = pairs(&values, &[1.0; 4]);
let heavy = pairs(&values, &[1.0, 1.0, 1.0, 3.0]);
let edges = [0.0, 50.0, 100.0];
let inverted_unweighted: Vec<f64> = edges
.iter()
.map(|&p| weighted_at(&unit, p, WeightedQuantileRule::InvertedCdf))
.collect();
assert_eq!(inverted_unweighted, vec![1.0, 2.0, 10.0]);
let inverted_weighted: Vec<f64> = edges
.iter()
.map(|&p| weighted_at(&heavy, p, WeightedQuantileRule::InvertedCdf))
.collect();
assert_eq!(inverted_weighted, vec![1.0, 3.0, 10.0]);
let averaged_unweighted: Vec<f64> = edges
.iter()
.map(|&p| weighted_at(&unit, p, WeightedQuantileRule::AveragedInvertedCdf))
.collect();
assert_eq!(averaged_unweighted, vec![1.0, 2.5, 10.0]);
let averaged_weighted: Vec<f64> = edges
.iter()
.map(|&p| weighted_at(&heavy, p, WeightedQuantileRule::AveragedInvertedCdf))
.collect();
assert_eq!(averaged_weighted, vec![1.0, 6.5, 10.0]);
}
#[test]
fn the_unweighted_step_rule_is_the_unit_weight_case_and_leaves_the_linear_one() {
let sample = [0.0, 1.0, 2.0, 10.0];
let unit = pairs(&sample, &[1.0; 4]);
for percentile in DIVERGENT {
let unweighted = averaged_at(&sample, percentile);
let weighted =
weighted_at(&unit, percentile, WeightedQuantileRule::AveragedInvertedCdf);
assert_eq!(
unweighted.to_bits(),
weighted.to_bits(),
"Q({percentile}) disagreed between the unweighted rule and \
its own unit-weight case"
);
}
assert_eq!(averaged_at(&sample, 25.0), 0.5);
assert_eq!(linear_at(&sample, 25.0), 0.75);
assert_eq!(averaged_at(&sample, 75.0), 6.0);
assert_eq!(linear_at(&sample, 75.0), 4.0);
assert_eq!(averaged_at(&sample, 50.0), linear_at(&sample, 50.0));
}
#[test]
fn an_integer_weight_is_a_repeated_row() {
let values = [1.0, 2.0, 3.0, 10.0];
let weighted = pairs(&values, &[1.0, 2.0, 1.0, 3.0]);
let repeated = pairs(&[1.0, 2.0, 2.0, 3.0, 10.0, 10.0, 10.0], &[1.0; 7]);
let mut averaged_disagreements = 0;
for step in 0..=100 {
let percentile = f64::from(step);
assert_eq!(
weighted_at(&weighted, percentile, WeightedQuantileRule::InvertedCdf),
weighted_at(&repeated, percentile, WeightedQuantileRule::InvertedCdf),
"the inverted CDF must reproduce row repetition bit for bit \
at p = {percentile}"
);
let rule = WeightedQuantileRule::AveragedInvertedCdf;
let from_weights = weighted_at(&weighted, percentile, rule);
let from_rows = weighted_at(&repeated, percentile, rule);
assert!(
(from_weights - from_rows).abs() <= 8.9e-16 * from_rows.abs().max(1.0),
"the averaged rule left its recorded rounding envelope at \
p = {percentile}: {from_weights} against {from_rows}"
);
averaged_disagreements +=
usize::from(from_weights.to_bits() != from_rows.to_bits());
}
assert_eq!(
averaged_disagreements, 0,
"on this sample the averaging rule happens to agree bit for \
bit; the envelope above is what is claimed, and this counter \
records what was observed rather than asserting exactness"
);
}
#[test]
fn fractional_and_zero_weights_behave_as_a_running_weight_should() {
let values = [1.0, 2.0, 3.0, 10.0];
let fractional = pairs(&values, &[0.25, 0.5, 0.25, 7.5]);
assert_eq!(
weighted_at(&fractional, 50.0, WeightedQuantileRule::InvertedCdf),
10.0
);
let zeroed = pairs(&values, &[1.0, 0.0, 0.0, 1.0]);
assert_eq!(
weighted_at(&zeroed, 25.0, WeightedQuantileRule::InvertedCdf),
1.0
);
assert_eq!(
weighted_at(&zeroed, 75.0, WeightedQuantileRule::InvertedCdf),
10.0
);
}
#[test]
fn a_single_value_is_every_percentile_of_itself_under_both_step_rules() {
let one = [(5.0, 3.0)];
for percentile in DIVERGENT {
assert_eq!(averaged_at(&[5.0], percentile), 5.0);
assert_eq!(
weighted_at(&one, percentile, WeightedQuantileRule::InvertedCdf),
5.0
);
assert_eq!(
weighted_at(&one, percentile, WeightedQuantileRule::AveragedInvertedCdf),
5.0
);
}
}
#[test]
fn the_endpoints_are_the_extrema_under_both_step_rules() {
let sample = [-3.0, 0.5, 2.0, 11.0];
let weighted = pairs(&sample, &[2.0, 1.0, 4.0, 0.5]);
for rule in [
WeightedQuantileRule::InvertedCdf,
WeightedQuantileRule::AveragedInvertedCdf,
] {
assert_eq!(weighted_at(&weighted, 0.0, rule), -3.0, "{rule:?} at p=0");
assert_eq!(
weighted_at(&weighted, 100.0, rule),
11.0,
"{rule:?} at p=100"
);
}
assert_eq!(averaged_at(&sample, 0.0), -3.0);
assert_eq!(averaged_at(&sample, 100.0), 11.0);
}
#[test]
fn ties_collapse_the_midpoint_branch_onto_themselves() {
let sample = [0.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 100.0];
assert_eq!(averaged_at(&sample, 25.0), 5.0);
assert_eq!(averaged_at(&sample, 50.0), 5.0);
assert_eq!(averaged_at(&sample, 75.0), 5.0);
}
#[test]
fn the_step_rules_are_monotone_and_actually_step() {
let sample = [-7.5, -0.25, 0.0, 1.0, 3.5, 12.0, 900.0, 1e6];
let mut previous = f64::NEG_INFINITY;
let mut distinct = 0_usize;
for step in 0..=1_000 {
let value = averaged_at(&sample, f64::from(step) / 10.0);
assert!(value >= previous, "the sweep fell back at step {step}");
distinct += usize::from(previous.is_finite() && value > previous);
previous = value;
}
assert_eq!(
previous,
sample[sample.len() - 1],
"the sweep ends at the top"
);
assert!(
(1..=2 * sample.len()).contains(&distinct),
"the sweep rose {distinct} times; a step rule over {} values \
rises a bounded number of times, and a constant or a \
continuous rule would fall outside that",
sample.len()
);
}
#[test]
#[should_panic = "a quantile needs at least one value"]
fn an_empty_weighted_sample_fails() {
let _ = weighted_at(&[], 50.0, WeightedQuantileRule::InvertedCdf);
}
#[test]
#[should_panic = "percentile 110 is outside"]
fn an_out_of_range_weighted_percentile_fails() {
let sample = pairs(&[0.0, 1.0], &[1.0, 1.0]);
let _ = weighted_at(&sample, 110.0, WeightedQuantileRule::InvertedCdf);
}
#[test]
#[should_panic = "total 0"]
fn an_all_zero_weight_vector_fails_instead_of_reading_an_arbitrary_index() {
let sample = pairs(&[0.0, 1.0, 2.0], &[0.0, 0.0, 0.0]);
let _ = weighted_at(&sample, 50.0, WeightedQuantileRule::InvertedCdf);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic = "not ascending"]
fn a_descending_weighted_sample_fails_in_a_debug_build() {
let sample = pairs(&[1.0, 0.0], &[1.0, 1.0]);
let _ = weighted_at(&sample, 50.0, WeightedQuantileRule::InvertedCdf);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic = "non-monotone"]
fn a_negative_weight_fails_in_a_debug_build() {
let sample = pairs(&[0.0, 1.0], &[1.0, -1.0]);
let _ = weighted_at(&sample, 50.0, WeightedQuantileRule::InvertedCdf);
}
#[test]
fn sorting_keeps_each_weight_with_its_value() {
let mut scratch = [(10.0, 3.0), (1.0, 1.0), (3.0, 1.0), (2.0, 1.0)];
sort_weighted_for_quantiles(&mut scratch);
assert_eq!(scratch, [(1.0, 1.0), (2.0, 1.0), (3.0, 1.0), (10.0, 3.0)]);
assert_eq!(
weighted_at(&scratch, 50.0, WeightedQuantileRule::AveragedInvertedCdf),
6.5,
"the worked example, reached through the sort rather than \
through a hand-ordered literal"
);
}
#[test]
fn equal_values_keep_their_input_order_so_the_running_weight_is_fixed() {
let mut scratch = [(5.0, 1.0), (5.0, 2.0), (5.0, 3.0), (1.0, 1.0)];
sort_weighted_for_quantiles(&mut scratch);
assert_eq!(
scratch,
[(1.0, 1.0), (5.0, 1.0), (5.0, 2.0), (5.0, 3.0)],
"the three equal values kept the order they were given in"
);
}
}
#[test]
fn the_median_uses_the_general_expression_rather_than_a_midpoint_branch() {
let mut disagreements = 0;
for step in 1..2_000 {
let lower = f64::from(step) / 7.0;
let upper = lower * 3.0 + 1.0 / 3.0;
let general = lower + 0.5 * (upper - lower);
let midpoint = (lower + upper) / 2.0;
let actual = linear_at(&[lower, upper], 50.0);
assert_eq!(
actual.to_bits(),
general.to_bits(),
"median of [{lower}, {upper}] left the general expression"
);
disagreements += usize::from(general.to_bits() != midpoint.to_bits());
}
assert!(
disagreements > 0,
"the midpoint form never disagreed, so this test proves nothing"
);
}
}