#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum QuantileRule {
Linear,
}
pub(crate) fn sort_for_quantiles(scratch: &mut [f64]) {
scratch.sort_unstable_by(f64::total_cmp);
}
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),
}
}
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());
}
#[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"
);
}
}