1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 #![allow(missing_docs)]
12 #![allow(deprecated)] // Float
14 use std
::cmp
::Ordering
::{self, Equal, Greater, Less}
;
17 fn local_cmp(x
: f64, y
: f64) -> Ordering
{
18 // arbitrarily decide that NaNs are larger than everything.
21 } else if x
.is_nan() {
32 fn local_sort(v
: &mut [f64]) {
33 v
.sort_by(|x
: &f64, y
: &f64| local_cmp(*x
, *y
));
36 /// Trait that provides simple descriptive statistics on a univariate set of numeric samples.
38 /// Sum of the samples.
40 /// Note: this method sacrifices performance at the altar of accuracy
41 /// Depends on IEEE-754 arithmetic guarantees. See proof of correctness at:
42 /// ["Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates"]
43 /// (http://www.cs.cmu.edu/~quake-papers/robust-arithmetic.ps)
46 /// Minimum value of the samples.
49 /// Maximum value of the samples.
52 /// Arithmetic mean (average) of the samples: sum divided by sample-count.
54 /// See: https://en.wikipedia.org/wiki/Arithmetic_mean
55 fn mean(&self) -> f64;
57 /// Median of the samples: value separating the lower half of the samples from the higher half.
58 /// Equal to `self.percentile(50.0)`.
60 /// See: https://en.wikipedia.org/wiki/Median
61 fn median(&self) -> f64;
63 /// Variance of the samples: bias-corrected mean of the squares of the differences of each
64 /// sample from the sample mean. Note that this calculates the _sample variance_ rather than the
65 /// population variance, which is assumed to be unknown. It therefore corrects the `(n-1)/n`
66 /// bias that would appear if we calculated a population variance, by dividing by `(n-1)` rather
69 /// See: https://en.wikipedia.org/wiki/Variance
72 /// Standard deviation: the square root of the sample variance.
74 /// Note: this is not a robust statistic for non-normal distributions. Prefer the
75 /// `median_abs_dev` for unknown distributions.
77 /// See: https://en.wikipedia.org/wiki/Standard_deviation
78 fn std_dev(&self) -> f64;
80 /// Standard deviation as a percent of the mean value. See `std_dev` and `mean`.
82 /// Note: this is not a robust statistic for non-normal distributions. Prefer the
83 /// `median_abs_dev_pct` for unknown distributions.
84 fn std_dev_pct(&self) -> f64;
86 /// Scaled median of the absolute deviations of each sample from the sample median. This is a
87 /// robust (distribution-agnostic) estimator of sample variability. Use this in preference to
88 /// `std_dev` if you cannot assume your sample is normally distributed. Note that this is scaled
89 /// by the constant `1.4826` to allow its use as a consistent estimator for the standard
92 /// See: http://en.wikipedia.org/wiki/Median_absolute_deviation
93 fn median_abs_dev(&self) -> f64;
95 /// Median absolute deviation as a percent of the median. See `median_abs_dev` and `median`.
96 fn median_abs_dev_pct(&self) -> f64;
98 /// Percentile: the value below which `pct` percent of the values in `self` fall. For example,
99 /// percentile(95.0) will return the value `v` such that 95% of the samples `s` in `self`
100 /// satisfy `s <= v`.
102 /// Calculated by linear interpolation between closest ranks.
104 /// See: http://en.wikipedia.org/wiki/Percentile
105 fn percentile(&self, pct
: f64) -> f64;
107 /// Quartiles of the sample: three values that divide the sample into four equal groups, each
108 /// with 1/4 of the data. The middle value is the median. See `median` and `percentile`. This
109 /// function may calculate the 3 quartiles more efficiently than 3 calls to `percentile`, but
110 /// is otherwise equivalent.
112 /// See also: https://en.wikipedia.org/wiki/Quartile
113 fn quartiles(&self) -> (f64, f64, f64);
115 /// Inter-quartile range: the difference between the 25th percentile (1st quartile) and the 75th
116 /// percentile (3rd quartile). See `quartiles`.
118 /// See also: https://en.wikipedia.org/wiki/Interquartile_range
119 fn iqr(&self) -> f64;
122 /// Extracted collection of all the summary statistics of a sample set.
123 #[derive(Clone, PartialEq, Copy)]
124 #[allow(missing_docs)]
133 pub std_dev_pct
: f64,
134 pub median_abs_dev
: f64,
135 pub median_abs_dev_pct
: f64,
136 pub quartiles
: (f64, f64, f64),
141 /// Construct a new summary of a sample set.
142 pub fn new(samples
: &[f64]) -> Summary
{
147 mean
: samples
.mean(),
148 median
: samples
.median(),
150 std_dev
: samples
.std_dev(),
151 std_dev_pct
: samples
.std_dev_pct(),
152 median_abs_dev
: samples
.median_abs_dev(),
153 median_abs_dev_pct
: samples
.median_abs_dev_pct(),
154 quartiles
: samples
.quartiles(),
160 impl Stats
for [f64] {
161 // FIXME #11059 handle NaN, inf and overflow
162 fn sum(&self) -> f64 {
163 let mut partials
= vec
![];
168 // This inner loop applies `hi`/`lo` summation to each
169 // partial so that the list of partial sums remains exact.
170 for i
in 0..partials
.len() {
171 let mut y
: f64 = partials
[i
];
172 if x
.abs() < y
.abs() {
173 mem
::swap(&mut x
, &mut y
);
175 // Rounded `x+y` is stored in `hi` with round-off stored in
176 // `lo`. Together `hi+lo` are exactly equal to `x+y`.
178 let lo
= y
- (hi
- x
);
185 if j
>= partials
.len() {
189 partials
.truncate(j
+ 1);
193 partials
.iter().fold(zero
, |p
, q
| p
+ *q
)
196 fn min(&self) -> f64 {
197 assert
!(!self.is_empty());
198 self.iter().fold(self[0], |p
, q
| p
.min(*q
))
201 fn max(&self) -> f64 {
202 assert
!(!self.is_empty());
203 self.iter().fold(self[0], |p
, q
| p
.max(*q
))
206 fn mean(&self) -> f64 {
207 assert
!(!self.is_empty());
208 self.sum() / (self.len() as f64)
211 fn median(&self) -> f64 {
212 self.percentile(50 as f64)
215 fn var(&self) -> f64 {
219 let mean
= self.mean();
220 let mut v
: f64 = 0.0;
225 // NB: this is _supposed to be_ len-1, not len. If you
226 // change it back to len, you will be calculating a
227 // population variance, not a sample variance.
228 let denom
= (self.len() - 1) as f64;
233 fn std_dev(&self) -> f64 {
237 fn std_dev_pct(&self) -> f64 {
238 let hundred
= 100 as f64;
239 (self.std_dev() / self.mean()) * hundred
242 fn median_abs_dev(&self) -> f64 {
243 let med
= self.median();
244 let abs_devs
: Vec
<f64> = self.iter().map(|&v
| (med
- v
).abs()).collect();
245 // This constant is derived by smarter statistics brains than me, but it is
246 // consistent with how R and other packages treat the MAD.
248 abs_devs
.median() * number
251 fn median_abs_dev_pct(&self) -> f64 {
252 let hundred
= 100 as f64;
253 (self.median_abs_dev() / self.median()) * hundred
256 fn percentile(&self, pct
: f64) -> f64 {
257 let mut tmp
= self.to_vec();
258 local_sort(&mut tmp
);
259 percentile_of_sorted(&tmp
, pct
)
262 fn quartiles(&self) -> (f64, f64, f64) {
263 let mut tmp
= self.to_vec();
264 local_sort(&mut tmp
);
266 let a
= percentile_of_sorted(&tmp
, first
);
268 let b
= percentile_of_sorted(&tmp
, secound
);
270 let c
= percentile_of_sorted(&tmp
, third
);
274 fn iqr(&self) -> f64 {
275 let (a
, _
, c
) = self.quartiles();
281 // Helper function: extract a value representing the `pct` percentile of a sorted sample-set, using
282 // linear interpolation. If samples are not sorted, return nonsensical value.
283 fn percentile_of_sorted(sorted_samples
: &[f64], pct
: f64) -> f64 {
284 assert
!(!sorted_samples
.is_empty());
285 if sorted_samples
.len() == 1 {
286 return sorted_samples
[0];
289 assert
!(zero
<= pct
);
290 let hundred
= 100f64;
291 assert
!(pct
<= hundred
);
293 return sorted_samples
[sorted_samples
.len() - 1];
295 let length
= (sorted_samples
.len() - 1) as f64;
296 let rank
= (pct
/ hundred
) * length
;
297 let lrank
= rank
.floor();
298 let d
= rank
- lrank
;
299 let n
= lrank
as usize;
300 let lo
= sorted_samples
[n
];
301 let hi
= sorted_samples
[n
+ 1];
306 /// Winsorize a set of samples, replacing values above the `100-pct` percentile
307 /// and below the `pct` percentile with those percentiles themselves. This is a
308 /// way of minimizing the effect of outliers, at the cost of biasing the sample.
309 /// It differs from trimming in that it does not change the number of samples,
310 /// just changes the values of those that are outliers.
312 /// See: http://en.wikipedia.org/wiki/Winsorising
313 pub fn winsorize(samples
: &mut [f64], pct
: f64) {
314 let mut tmp
= samples
.to_vec();
315 local_sort(&mut tmp
);
316 let lo
= percentile_of_sorted(&tmp
, pct
);
317 let hundred
= 100 as f64;
318 let hi
= percentile_of_sorted(&tmp
, hundred
- pct
);
319 for samp
in samples
{
322 } else if *samp
< lo
{
328 // Test vectors generated from R, using the script src/etc/stat-test-vectors.r.
335 use std
::io
::prelude
::*;
338 macro_rules
! assert_approx_eq
{
339 ($a
:expr
, $b
:expr
) => ({
340 let (a
, b
) = (&$a
, &$b
);
341 assert
!((*a
- *b
).abs() < 1.0e-6,
342 "{} is not approximately equal to {}", *a
, *b
);
346 fn check(samples
: &[f64], summ
: &Summary
) {
348 let summ2
= Summary
::new(samples
);
350 let mut w
= io
::sink();
352 (write
!(w
, "\n")).unwrap();
354 assert_eq
!(summ
.sum
, summ2
.sum
);
355 assert_eq
!(summ
.min
, summ2
.min
);
356 assert_eq
!(summ
.max
, summ2
.max
);
357 assert_eq
!(summ
.mean
, summ2
.mean
);
358 assert_eq
!(summ
.median
, summ2
.median
);
360 // We needed a few more digits to get exact equality on these
361 // but they're within float epsilon, which is 1.0e-6.
362 assert_approx_eq
!(summ
.var
, summ2
.var
);
363 assert_approx_eq
!(summ
.std_dev
, summ2
.std_dev
);
364 assert_approx_eq
!(summ
.std_dev_pct
, summ2
.std_dev_pct
);
365 assert_approx_eq
!(summ
.median_abs_dev
, summ2
.median_abs_dev
);
366 assert_approx_eq
!(summ
.median_abs_dev_pct
, summ2
.median_abs_dev_pct
);
368 assert_eq
!(summ
.quartiles
, summ2
.quartiles
);
369 assert_eq
!(summ
.iqr
, summ2
.iqr
);
373 fn test_min_max_nan() {
374 let xs
= &[1.0, 2.0, f64::NAN
, 3.0, 4.0];
375 let summary
= Summary
::new(xs
);
376 assert_eq
!(summary
.min
, 1.0);
377 assert_eq
!(summary
.max
, 4.0);
382 let val
= &[958.0000000000, 924.0000000000];
383 let summ
= &Summary
{
384 sum
: 1882.0000000000,
387 mean
: 941.0000000000,
388 median
: 941.0000000000,
390 std_dev
: 24.0416305603,
391 std_dev_pct
: 2.5549022912,
392 median_abs_dev
: 25.2042000000,
393 median_abs_dev_pct
: 2.6784484591,
394 quartiles
: (932.5000000000, 941.0000000000, 949.5000000000),
400 fn test_norm10narrow() {
401 let val
= &[966.0000000000,
411 let summ
= &Summary
{
412 sum
: 9996.0000000000,
414 max
: 1217.0000000000,
415 mean
: 999.6000000000,
416 median
: 970.5000000000,
417 var
: 16050.7111111111,
418 std_dev
: 126.6914010938,
419 std_dev_pct
: 12.6742097933,
420 median_abs_dev
: 102.2994000000,
421 median_abs_dev_pct
: 10.5408964451,
422 quartiles
: (956.7500000000, 970.5000000000, 1078.7500000000),
428 fn test_norm10medium() {
429 let val
= &[954.0000000000,
439 let summ
= &Summary
{
440 sum
: 8653.0000000000,
442 max
: 1084.0000000000,
443 mean
: 865.3000000000,
444 median
: 911.5000000000,
445 var
: 48628.4555555556,
446 std_dev
: 220.5186059170,
447 std_dev_pct
: 25.4846418487,
448 median_abs_dev
: 195.7032000000,
449 median_abs_dev_pct
: 21.4704552935,
450 quartiles
: (771.0000000000, 911.5000000000, 1017.2500000000),
456 fn test_norm10wide() {
457 let val
= &[505.0000000000,
467 let summ
= &Summary
{
468 sum
: 9349.0000000000,
470 max
: 1591.0000000000,
471 mean
: 934.9000000000,
472 median
: 913.5000000000,
473 var
: 239208.9888888889,
474 std_dev
: 489.0899599142,
475 std_dev_pct
: 52.3146817750,
476 median_abs_dev
: 611.5725000000,
477 median_abs_dev_pct
: 66.9482758621,
478 quartiles
: (567.2500000000, 913.5000000000, 1331.2500000000),
484 fn test_norm25verynarrow() {
485 let val
= &[991.0000000000,
510 let summ
= &Summary
{
511 sum
: 24926.0000000000,
513 max
: 1040.0000000000,
514 mean
: 997.0400000000,
515 median
: 998.0000000000,
517 std_dev
: 19.8294393937,
518 std_dev_pct
: 1.9888308788,
519 median_abs_dev
: 22.2390000000,
520 median_abs_dev_pct
: 2.2283567134,
521 quartiles
: (983.0000000000, 998.0000000000, 1013.0000000000),
528 let val
= &[23.0000000000,
538 let summ
= &Summary
{
543 median
: 11.5000000000,
545 std_dev
: 16.9643416875,
546 std_dev_pct
: 101.5828843560,
547 median_abs_dev
: 13.3434000000,
548 median_abs_dev_pct
: 116.0295652174,
549 quartiles
: (4.2500000000, 11.5000000000, 22.5000000000),
556 let val
= &[24.0000000000,
566 let summ
= &Summary
{
571 median
: 24.5000000000,
573 std_dev
: 19.5848580967,
574 std_dev_pct
: 74.4671410520,
575 median_abs_dev
: 22.9803000000,
576 median_abs_dev_pct
: 93.7971428571,
577 quartiles
: (9.5000000000, 24.5000000000, 36.5000000000),
584 let val
= &[71.0000000000,
594 let summ
= &Summary
{
599 median
: 22.0000000000,
601 std_dev
: 21.4050876611,
602 std_dev_pct
: 88.4507754589,
603 median_abs_dev
: 21.4977000000,
604 median_abs_dev_pct
: 97.7168181818,
605 quartiles
: (7.7500000000, 22.0000000000, 35.0000000000),
612 let val
= &[3.0000000000,
637 let summ
= &Summary
{
642 median
: 19.0000000000,
644 std_dev
: 24.5161851301,
645 std_dev_pct
: 103.3565983562,
646 median_abs_dev
: 19.2738000000,
647 median_abs_dev_pct
: 101.4410526316,
648 quartiles
: (6.0000000000, 19.0000000000, 31.0000000000),
655 let val
= &[18.0000000000,
680 let summ
= &Summary
{
685 median
: 20.0000000000,
687 std_dev
: 4.5650848842,
688 std_dev_pct
: 22.2037202539,
689 median_abs_dev
: 5.9304000000,
690 median_abs_dev_pct
: 29.6520000000,
691 quartiles
: (17.0000000000, 20.0000000000, 24.0000000000),
697 fn test_pois25lambda30() {
698 let val
= &[27.0000000000,
723 let summ
= &Summary
{
728 median
: 32.0000000000,
730 std_dev
: 5.1568724372,
731 std_dev_pct
: 16.3814245145,
732 median_abs_dev
: 5.9304000000,
733 median_abs_dev_pct
: 18.5325000000,
734 quartiles
: (28.0000000000, 32.0000000000, 34.0000000000),
740 fn test_pois25lambda40() {
741 let val
= &[42.0000000000,
766 let summ
= &Summary
{
767 sum
: 1019.0000000000,
771 median
: 42.0000000000,
773 std_dev
: 5.8685603004,
774 std_dev_pct
: 14.3978417577,
775 median_abs_dev
: 5.9304000000,
776 median_abs_dev_pct
: 14.1200000000,
777 quartiles
: (37.0000000000, 42.0000000000, 45.0000000000),
783 fn test_pois25lambda50() {
784 let val
= &[45.0000000000,
809 let summ
= &Summary
{
810 sum
: 1235.0000000000,
814 median
: 50.0000000000,
816 std_dev
: 5.6273143387,
817 std_dev_pct
: 11.3913245723,
818 median_abs_dev
: 4.4478000000,
819 median_abs_dev_pct
: 8.8956000000,
820 quartiles
: (44.0000000000, 50.0000000000, 52.0000000000),
827 let val
= &[99.0000000000,
852 let summ
= &Summary
{
853 sum
: 1242.0000000000,
857 median
: 45.0000000000,
858 var
: 1015.6433333333,
859 std_dev
: 31.8691595957,
860 std_dev_pct
: 64.1488719719,
861 median_abs_dev
: 45.9606000000,
862 median_abs_dev_pct
: 102.1346666667,
863 quartiles
: (29.0000000000, 45.0000000000, 79.0000000000),
871 assert_eq
!([0.5f64, 3.2321f64, 1.5678f64].sum(), 5.2999);
874 fn test_sum_f64_between_ints_that_sum_to_0() {
875 assert_eq
!([1e30f64
, 1.2f64, -1e30f64
].sum(), 1.2);
885 pub fn sum_three_items(b
: &mut Bencher
) {
887 [1e20f64
, 1.5f64, -1e20f64
].sum();
891 pub fn sum_many_f64(b
: &mut Bencher
) {
892 let nums
= [-1e30f64
, 1e60
, 1e30
, 1.0, -1e60
];
893 let v
= (0..500).map(|i
| nums
[i
% 5]).collect
::<Vec
<_
>>();
901 pub fn no_iter(_
: &mut Bencher
) {}