library/test/src/stats.rs

   1 #![allow(missing_docs)]
   2 #![allow(deprecated)] // Float
   3
   4 use std::mem;
   5
   6 #[cfg(test)]
   7 mod tests;
   8
   9 fn local_sort(v: &mut [f64]) {
  10     v.sort_by(|x: &f64, y: &f64| x.total_cmp(y));
  11 }
  12
  13 /// Trait that provides simple descriptive statistics on a univariate set of numeric samples.
  14 pub trait Stats {
  15     /// Sum of the samples.
  16     ///
  17     /// Note: this method sacrifices performance at the altar of accuracy
  18     /// Depends on IEEE-754 arithmetic guarantees. See proof of correctness at:
  19     /// ["Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric
  20     /// Predicates"][paper]
  21     ///
  22     /// [paper]: http://www.cs.cmu.edu/~quake-papers/robust-arithmetic.ps
  23     fn sum(&self) -> f64;
  24
  25     /// Minimum value of the samples.
  26     fn min(&self) -> f64;
  27
  28     /// Maximum value of the samples.
  29     fn max(&self) -> f64;
  30
  31     /// Arithmetic mean (average) of the samples: sum divided by sample-count.
  32     ///
  33     /// See: <https://en.wikipedia.org/wiki/Arithmetic_mean>
  34     fn mean(&self) -> f64;
  35
  36     /// Median of the samples: value separating the lower half of the samples from the higher half.
  37     /// Equal to `self.percentile(50.0)`.
  38     ///
  39     /// See: <https://en.wikipedia.org/wiki/Median>
  40     fn median(&self) -> f64;
  41
  42     /// Variance of the samples: bias-corrected mean of the squares of the differences of each
  43     /// sample from the sample mean. Note that this calculates the _sample variance_ rather than the
  44     /// population variance, which is assumed to be unknown. It therefore corrects the `(n-1)/n`
  45     /// bias that would appear if we calculated a population variance, by dividing by `(n-1)` rather
  46     /// than `n`.
  47     ///
  48     /// See: <https://en.wikipedia.org/wiki/Variance>
  49     fn var(&self) -> f64;
  50
  51     /// Standard deviation: the square root of the sample variance.
  52     ///
  53     /// Note: this is not a robust statistic for non-normal distributions. Prefer the
  54     /// `median_abs_dev` for unknown distributions.
  55     ///
  56     /// See: <https://en.wikipedia.org/wiki/Standard_deviation>
  57     fn std_dev(&self) -> f64;
  58
  59     /// Standard deviation as a percent of the mean value. See `std_dev` and `mean`.
  60     ///
  61     /// Note: this is not a robust statistic for non-normal distributions. Prefer the
  62     /// `median_abs_dev_pct` for unknown distributions.
  63     fn std_dev_pct(&self) -> f64;
  64
  65     /// Scaled median of the absolute deviations of each sample from the sample median. This is a
  66     /// robust (distribution-agnostic) estimator of sample variability. Use this in preference to
  67     /// `std_dev` if you cannot assume your sample is normally distributed. Note that this is scaled
  68     /// by the constant `1.4826` to allow its use as a consistent estimator for the standard
  69     /// deviation.
  70     ///
  71     /// See: <https://en.wikipedia.org/wiki/Median_absolute_deviation>
  72     fn median_abs_dev(&self) -> f64;
  73
  74     /// Median absolute deviation as a percent of the median. See `median_abs_dev` and `median`.
  75     fn median_abs_dev_pct(&self) -> f64;
  76
  77     /// Percentile: the value below which `pct` percent of the values in `self` fall. For example,
  78     /// percentile(95.0) will return the value `v` such that 95% of the samples `s` in `self`
  79     /// satisfy `s <= v`.
  80     ///
  81     /// Calculated by linear interpolation between closest ranks.
  82     ///
  83     /// See: <https://en.wikipedia.org/wiki/Percentile>
  84     fn percentile(&self, pct: f64) -> f64;
  85
  86     /// Quartiles of the sample: three values that divide the sample into four equal groups, each
  87     /// with 1/4 of the data. The middle value is the median. See `median` and `percentile`. This
  88     /// function may calculate the 3 quartiles more efficiently than 3 calls to `percentile`, but
  89     /// is otherwise equivalent.
  90     ///
  91     /// See also: <https://en.wikipedia.org/wiki/Quartile>
  92     fn quartiles(&self) -> (f64, f64, f64);
  93
  94     /// Inter-quartile range: the difference between the 25th percentile (1st quartile) and the 75th
  95     /// percentile (3rd quartile). See `quartiles`.
  96     ///
  97     /// See also: <https://en.wikipedia.org/wiki/Interquartile_range>
  98     fn iqr(&self) -> f64;
  99 }
 100
 101 /// Extracted collection of all the summary statistics of a sample set.
 102 #[derive(Debug, Clone, PartialEq, Copy)]
 103 #[allow(missing_docs)]
 104 pub struct Summary {
 105     pub sum: f64,
 106     pub min: f64,
 107     pub max: f64,
 108     pub mean: f64,
 109     pub median: f64,
 110     pub var: f64,
 111     pub std_dev: f64,
 112     pub std_dev_pct: f64,
 113     pub median_abs_dev: f64,
 114     pub median_abs_dev_pct: f64,
 115     pub quartiles: (f64, f64, f64),
 116     pub iqr: f64,
 117 }
 118
 119 impl Summary {
 120     /// Construct a new summary of a sample set.
 121     pub fn new(samples: &[f64]) -> Summary {
 122         Summary {
 123             sum: samples.sum(),
 124             min: samples.min(),
 125             max: samples.max(),
 126             mean: samples.mean(),
 127             median: samples.median(),
 128             var: samples.var(),
 129             std_dev: samples.std_dev(),
 130             std_dev_pct: samples.std_dev_pct(),
 131             median_abs_dev: samples.median_abs_dev(),
 132             median_abs_dev_pct: samples.median_abs_dev_pct(),
 133             quartiles: samples.quartiles(),
 134             iqr: samples.iqr(),
 135         }
 136     }
 137 }
 138
 139 impl Stats for [f64] {
 140     // FIXME #11059 handle NaN, inf and overflow
 141     fn sum(&self) -> f64 {
 142         let mut partials = vec![];
 143
 144         for &x in self {
 145             let mut x = x;
 146             let mut j = 0;
 147             // This inner loop applies `hi`/`lo` summation to each
 148             // partial so that the list of partial sums remains exact.
 149             for i in 0..partials.len() {
 150                 let mut y: f64 = partials[i];
 151                 if x.abs() < y.abs() {
 152                     mem::swap(&mut x, &mut y);
 153                 }
 154                 // Rounded `x+y` is stored in `hi` with round-off stored in
 155                 // `lo`. Together `hi+lo` are exactly equal to `x+y`.
 156                 let hi = x + y;
 157                 let lo = y - (hi - x);
 158                 if lo != 0.0 {
 159                     partials[j] = lo;
 160                     j += 1;
 161                 }
 162                 x = hi;
 163             }
 164             if j >= partials.len() {
 165                 partials.push(x);
 166             } else {
 167                 partials[j] = x;
 168                 partials.truncate(j + 1);
 169             }
 170         }
 171         let zero: f64 = 0.0;
 172         partials.iter().fold(zero, |p, q| p + *q)
 173     }
 174
 175     fn min(&self) -> f64 {
 176         assert!(!self.is_empty());
 177         self.iter().fold(self[0], |p, q| p.min(*q))
 178     }
 179
 180     fn max(&self) -> f64 {
 181         assert!(!self.is_empty());
 182         self.iter().fold(self[0], |p, q| p.max(*q))
 183     }
 184
 185     fn mean(&self) -> f64 {
 186         assert!(!self.is_empty());
 187         self.sum() / (self.len() as f64)
 188     }
 189
 190     fn median(&self) -> f64 {
 191         self.percentile(50_f64)
 192     }
 193
 194     fn var(&self) -> f64 {
 195         if self.len() < 2 {
 196             0.0
 197         } else {
 198             let mean = self.mean();
 199             let mut v: f64 = 0.0;
 200             for s in self {
 201                 let x = *s - mean;
 202                 v += x * x;
 203             }
 204             // N.B., this is _supposed to be_ len-1, not len. If you
 205             // change it back to len, you will be calculating a
 206             // population variance, not a sample variance.
 207             let denom = (self.len() - 1) as f64;
 208             v / denom
 209         }
 210     }
 211
 212     fn std_dev(&self) -> f64 {
 213         self.var().sqrt()
 214     }
 215
 216     fn std_dev_pct(&self) -> f64 {
 217         let hundred = 100_f64;
 218         (self.std_dev() / self.mean()) * hundred
 219     }
 220
 221     fn median_abs_dev(&self) -> f64 {
 222         let med = self.median();
 223         let abs_devs: Vec<f64> = self.iter().map(|&v| (med - v).abs()).collect();
 224         // This constant is derived by smarter statistics brains than me, but it is
 225         // consistent with how R and other packages treat the MAD.
 226         let number = 1.4826;
 227         abs_devs.median() * number
 228     }
 229
 230     fn median_abs_dev_pct(&self) -> f64 {
 231         let hundred = 100_f64;
 232         (self.median_abs_dev() / self.median()) * hundred
 233     }
 234
 235     fn percentile(&self, pct: f64) -> f64 {
 236         let mut tmp = self.to_vec();
 237         local_sort(&mut tmp);
 238         percentile_of_sorted(&tmp, pct)
 239     }
 240
 241     fn quartiles(&self) -> (f64, f64, f64) {
 242         let mut tmp = self.to_vec();
 243         local_sort(&mut tmp);
 244         let first = 25_f64;
 245         let a = percentile_of_sorted(&tmp, first);
 246         let second = 50_f64;
 247         let b = percentile_of_sorted(&tmp, second);
 248         let third = 75_f64;
 249         let c = percentile_of_sorted(&tmp, third);
 250         (a, b, c)
 251     }
 252
 253     fn iqr(&self) -> f64 {
 254         let (a, _, c) = self.quartiles();
 255         c - a
 256     }
 257 }
 258
 259 // Helper function: extract a value representing the `pct` percentile of a sorted sample-set, using
 260 // linear interpolation. If samples are not sorted, return nonsensical value.
 261 fn percentile_of_sorted(sorted_samples: &[f64], pct: f64) -> f64 {
 262     assert!(!sorted_samples.is_empty());
 263     if sorted_samples.len() == 1 {
 264         return sorted_samples[0];
 265     }
 266     let zero: f64 = 0.0;
 267     assert!(zero <= pct);
 268     let hundred = 100_f64;
 269     assert!(pct <= hundred);
 270     if pct == hundred {
 271         return sorted_samples[sorted_samples.len() - 1];
 272     }
 273     let length = (sorted_samples.len() - 1) as f64;
 274     let rank = (pct / hundred) * length;
 275     let lrank = rank.floor();
 276     let d = rank - lrank;
 277     let n = lrank as usize;
 278     let lo = sorted_samples[n];
 279     let hi = sorted_samples[n + 1];
 280     lo + (hi - lo) * d
 281 }
 282
 283 /// Winsorize a set of samples, replacing values above the `100-pct` percentile
 284 /// and below the `pct` percentile with those percentiles themselves. This is a
 285 /// way of minimizing the effect of outliers, at the cost of biasing the sample.
 286 /// It differs from trimming in that it does not change the number of samples,
 287 /// just changes the values of those that are outliers.
 288 ///
 289 /// See: <https://en.wikipedia.org/wiki/Winsorising>
 290 pub fn winsorize(samples: &mut [f64], pct: f64) {
 291     let mut tmp = samples.to_vec();
 292     local_sort(&mut tmp);
 293     let lo = percentile_of_sorted(&tmp, pct);
 294     let hundred = 100_f64;
 295     let hi = percentile_of_sorted(&tmp, hundred - pct);
 296     for samp in samples {
 297         if *samp > hi {
 298             *samp = hi
 299         } else if *samp < lo {
 300             *samp = lo
 301         }
 302     }
 303 }