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)]
13 use std
::cmp
::Ordering
::{self, Less, Greater, Equal}
;
14 use std
::collections
::hash_map
::Entry
::{Occupied, Vacant}
;
15 use std
::collections
::hash_map
;
18 use std
::num
::{Float, FromPrimitive}
;
20 fn local_cmp
<T
:Float
>(x
: T
, y
: T
) -> Ordering
{
21 // arbitrarily decide that NaNs are larger than everything.
24 } else if x
.is_nan() {
35 fn local_sort
<T
: Float
>(v
: &mut [T
]) {
36 v
.sort_by(|x
: &T
, y
: &T
| local_cmp(*x
, *y
));
39 /// Trait that provides simple descriptive statistics on a univariate set of numeric samples.
40 pub trait Stats
<T
: Float
+ FromPrimitive
> {
42 /// Sum of the samples.
44 /// Note: this method sacrifices performance at the altar of accuracy
45 /// Depends on IEEE-754 arithmetic guarantees. See proof of correctness at:
46 /// ["Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates"]
47 /// (http://www.cs.cmu.edu/~quake-papers/robust-arithmetic.ps)
48 /// *Discrete & Computational Geometry 18*, 3 (Oct 1997), 305-363, Shewchuk J.R.
51 /// Minimum value of the samples.
54 /// Maximum value of the samples.
57 /// Arithmetic mean (average) of the samples: sum divided by sample-count.
59 /// See: https://en.wikipedia.org/wiki/Arithmetic_mean
62 /// Median of the samples: value separating the lower half of the samples from the higher half.
63 /// Equal to `self.percentile(50.0)`.
65 /// See: https://en.wikipedia.org/wiki/Median
66 fn median(&self) -> T
;
68 /// Variance of the samples: bias-corrected mean of the squares of the differences of each
69 /// sample from the sample mean. Note that this calculates the _sample variance_ rather than the
70 /// population variance, which is assumed to be unknown. It therefore corrects the `(n-1)/n`
71 /// bias that would appear if we calculated a population variance, by dividing by `(n-1)` rather
74 /// See: https://en.wikipedia.org/wiki/Variance
77 /// Standard deviation: the square root of the sample variance.
79 /// Note: this is not a robust statistic for non-normal distributions. Prefer the
80 /// `median_abs_dev` for unknown distributions.
82 /// See: https://en.wikipedia.org/wiki/Standard_deviation
83 fn std_dev(&self) -> T
;
85 /// Standard deviation as a percent of the mean value. See `std_dev` and `mean`.
87 /// Note: this is not a robust statistic for non-normal distributions. Prefer the
88 /// `median_abs_dev_pct` for unknown distributions.
89 fn std_dev_pct(&self) -> T
;
91 /// Scaled median of the absolute deviations of each sample from the sample median. This is a
92 /// robust (distribution-agnostic) estimator of sample variability. Use this in preference to
93 /// `std_dev` if you cannot assume your sample is normally distributed. Note that this is scaled
94 /// by the constant `1.4826` to allow its use as a consistent estimator for the standard
97 /// See: http://en.wikipedia.org/wiki/Median_absolute_deviation
98 fn median_abs_dev(&self) -> T
;
100 /// Median absolute deviation as a percent of the median. See `median_abs_dev` and `median`.
101 fn median_abs_dev_pct(&self) -> T
;
103 /// Percentile: the value below which `pct` percent of the values in `self` fall. For example,
104 /// percentile(95.0) will return the value `v` such that 95% of the samples `s` in `self`
105 /// satisfy `s <= v`.
107 /// Calculated by linear interpolation between closest ranks.
109 /// See: http://en.wikipedia.org/wiki/Percentile
110 fn percentile(&self, pct
: T
) -> T
;
112 /// Quartiles of the sample: three values that divide the sample into four equal groups, each
113 /// with 1/4 of the data. The middle value is the median. See `median` and `percentile`. This
114 /// function may calculate the 3 quartiles more efficiently than 3 calls to `percentile`, but
115 /// is otherwise equivalent.
117 /// See also: https://en.wikipedia.org/wiki/Quartile
118 fn quartiles(&self) -> (T
,T
,T
);
120 /// Inter-quartile range: the difference between the 25th percentile (1st quartile) and the 75th
121 /// percentile (3rd quartile). See `quartiles`.
123 /// See also: https://en.wikipedia.org/wiki/Interquartile_range
127 /// Extracted collection of all the summary statistics of a sample set.
128 #[derive(Clone, PartialEq)]
129 #[allow(missing_docs)]
130 pub struct Summary
<T
> {
139 pub median_abs_dev
: T
,
140 pub median_abs_dev_pct
: T
,
141 pub quartiles
: (T
,T
,T
),
145 impl<T
: Float
+ FromPrimitive
> Summary
<T
> {
146 /// Construct a new summary of a sample set.
147 pub fn new(samples
: &[T
]) -> Summary
<T
> {
152 mean
: samples
.mean(),
153 median
: samples
.median(),
155 std_dev
: samples
.std_dev(),
156 std_dev_pct
: samples
.std_dev_pct(),
157 median_abs_dev
: samples
.median_abs_dev(),
158 median_abs_dev_pct
: samples
.median_abs_dev_pct(),
159 quartiles
: samples
.quartiles(),
165 impl<T
: Float
+ FromPrimitive
> Stats
<T
> for [T
] {
166 // FIXME #11059 handle NaN, inf and overflow
168 let mut partials
= vec
![];
173 // This inner loop applies `hi`/`lo` summation to each
174 // partial so that the list of partial sums remains exact.
175 for i
in 0..partials
.len() {
176 let mut y
: T
= partials
[i
];
177 if x
.abs() < y
.abs() {
178 mem
::swap(&mut x
, &mut y
);
180 // Rounded `x+y` is stored in `hi` with round-off stored in
181 // `lo`. Together `hi+lo` are exactly equal to `x+y`.
183 let lo
= y
- (hi
- x
);
184 if lo
!= Float
::zero() {
190 if j
>= partials
.len() {
194 partials
.truncate(j
+1);
197 let zero
: T
= Float
::zero();
198 partials
.iter().fold(zero
, |p
, q
| p
+ *q
)
202 assert
!(self.len() != 0);
203 self.iter().fold(self[0], |p
, q
| p
.min(*q
))
207 assert
!(self.len() != 0);
208 self.iter().fold(self[0], |p
, q
| p
.max(*q
))
211 fn mean(&self) -> T
{
212 assert
!(self.len() != 0);
213 self.sum() / FromPrimitive
::from_uint(self.len()).unwrap()
216 fn median(&self) -> T
{
217 self.percentile(FromPrimitive
::from_uint(50).unwrap())
224 let mean
= self.mean();
225 let mut v
: T
= Float
::zero();
230 // NB: this is _supposed to be_ len-1, not len. If you
231 // change it back to len, you will be calculating a
232 // population variance, not a sample variance.
233 let denom
= FromPrimitive
::from_uint(self.len()-1).unwrap();
238 fn std_dev(&self) -> T
{
242 fn std_dev_pct(&self) -> T
{
243 let hundred
= FromPrimitive
::from_uint(100).unwrap();
244 (self.std_dev() / self.mean()) * hundred
247 fn median_abs_dev(&self) -> T
{
248 let med
= self.median();
249 let abs_devs
: Vec
<T
> = self.iter().map(|&v
| (med
- v
).abs()).collect();
250 // This constant is derived by smarter statistics brains than me, but it is
251 // consistent with how R and other packages treat the MAD.
252 let number
= FromPrimitive
::from_f64(1.4826).unwrap();
253 abs_devs
.median() * number
256 fn median_abs_dev_pct(&self) -> T
{
257 let hundred
= FromPrimitive
::from_uint(100).unwrap();
258 (self.median_abs_dev() / self.median()) * hundred
261 fn percentile(&self, pct
: T
) -> T
{
262 let mut tmp
= self.to_vec();
263 local_sort(&mut tmp
);
264 percentile_of_sorted(&tmp
, pct
)
267 fn quartiles(&self) -> (T
,T
,T
) {
268 let mut tmp
= self.to_vec();
269 local_sort(&mut tmp
);
270 let first
= FromPrimitive
::from_uint(25).unwrap();
271 let a
= percentile_of_sorted(&tmp
, first
);
272 let secound
= FromPrimitive
::from_uint(50).unwrap();
273 let b
= percentile_of_sorted(&tmp
, secound
);
274 let third
= FromPrimitive
::from_uint(75).unwrap();
275 let c
= percentile_of_sorted(&tmp
, third
);
280 let (a
,_
,c
) = self.quartiles();
286 // Helper function: extract a value representing the `pct` percentile of a sorted sample-set, using
287 // linear interpolation. If samples are not sorted, return nonsensical value.
288 fn percentile_of_sorted
<T
: Float
+ FromPrimitive
>(sorted_samples
: &[T
],
290 assert
!(sorted_samples
.len() != 0);
291 if sorted_samples
.len() == 1 {
292 return sorted_samples
[0];
294 let zero
: T
= Float
::zero();
295 assert
!(zero
<= pct
);
296 let hundred
= FromPrimitive
::from_uint(100).unwrap();
297 assert
!(pct
<= hundred
);
299 return sorted_samples
[sorted_samples
.len() - 1];
301 let length
= FromPrimitive
::from_uint(sorted_samples
.len() - 1).unwrap();
302 let rank
= (pct
/ hundred
) * length
;
303 let lrank
= rank
.floor();
304 let d
= rank
- lrank
;
305 let n
= lrank
.to_uint().unwrap();
306 let lo
= sorted_samples
[n
];
307 let hi
= sorted_samples
[n
+1];
312 /// Winsorize a set of samples, replacing values above the `100-pct` percentile and below the `pct`
313 /// percentile with those percentiles themselves. This is a way of minimizing the effect of
314 /// outliers, at the cost of biasing the sample. It differs from trimming in that it does not
315 /// change the number of samples, just changes the values of those that are outliers.
317 /// See: http://en.wikipedia.org/wiki/Winsorising
318 pub fn winsorize
<T
: Float
+ FromPrimitive
>(samples
: &mut [T
], pct
: T
) {
319 let mut tmp
= samples
.to_vec();
320 local_sort(&mut tmp
);
321 let lo
= percentile_of_sorted(&tmp
, pct
);
322 let hundred
: T
= FromPrimitive
::from_uint(100).unwrap();
323 let hi
= percentile_of_sorted(&tmp
, hundred
-pct
);
324 for samp
in samples
{
327 } else if *samp
< lo
{
333 /// Returns a HashMap with the number of occurrences of every element in the
334 /// sequence that the iterator exposes.
335 pub fn freq_count
<T
, U
>(iter
: T
) -> hash_map
::HashMap
<U
, uint
>
336 where T
: Iterator
<Item
=U
>, U
: Eq
+ Clone
+ Hash
338 let mut map
: hash_map
::HashMap
<U
,uint
> = hash_map
::HashMap
::new();
340 match map
.entry(elem
) {
341 Occupied(mut entry
) => { *entry.get_mut() += 1; }
,
342 Vacant(entry
) => { entry.insert(1); }
,
348 // Test vectors generated from R, using the script src/etc/stat-test-vectors.r.
357 macro_rules
! assert_approx_eq
{
358 ($a
:expr
, $b
:expr
) => ({
360 let (a
, b
) = (&$a
, &$b
);
361 assert
!((*a
- *b
).abs() < 1.0e-6,
362 "{} is not approximately equal to {}", *a
, *b
);
366 fn check(samples
: &[f64], summ
: &Summary
<f64>) {
368 let summ2
= Summary
::new(samples
);
370 let mut w
= old_io
::stdout();
372 (write
!(w
, "\n")).unwrap();
374 assert_eq
!(summ
.sum
, summ2
.sum
);
375 assert_eq
!(summ
.min
, summ2
.min
);
376 assert_eq
!(summ
.max
, summ2
.max
);
377 assert_eq
!(summ
.mean
, summ2
.mean
);
378 assert_eq
!(summ
.median
, summ2
.median
);
380 // We needed a few more digits to get exact equality on these
381 // but they're within float epsilon, which is 1.0e-6.
382 assert_approx_eq
!(summ
.var
, summ2
.var
);
383 assert_approx_eq
!(summ
.std_dev
, summ2
.std_dev
);
384 assert_approx_eq
!(summ
.std_dev_pct
, summ2
.std_dev_pct
);
385 assert_approx_eq
!(summ
.median_abs_dev
, summ2
.median_abs_dev
);
386 assert_approx_eq
!(summ
.median_abs_dev_pct
, summ2
.median_abs_dev_pct
);
388 assert_eq
!(summ
.quartiles
, summ2
.quartiles
);
389 assert_eq
!(summ
.iqr
, summ2
.iqr
);
393 fn test_min_max_nan() {
394 let xs
= &[1.0, 2.0, f64::NAN
, 3.0, 4.0];
395 let summary
= Summary
::new(xs
);
396 assert_eq
!(summary
.min
, 1.0);
397 assert_eq
!(summary
.max
, 4.0);
406 let summ
= &Summary
{
407 sum
: 1882.0000000000,
410 mean
: 941.0000000000,
411 median
: 941.0000000000,
413 std_dev
: 24.0416305603,
414 std_dev_pct
: 2.5549022912,
415 median_abs_dev
: 25.2042000000,
416 median_abs_dev_pct
: 2.6784484591,
417 quartiles
: (932.5000000000,941.0000000000,949.5000000000),
423 fn test_norm10narrow() {
436 let summ
= &Summary
{
437 sum
: 9996.0000000000,
439 max
: 1217.0000000000,
440 mean
: 999.6000000000,
441 median
: 970.5000000000,
442 var
: 16050.7111111111,
443 std_dev
: 126.6914010938,
444 std_dev_pct
: 12.6742097933,
445 median_abs_dev
: 102.2994000000,
446 median_abs_dev_pct
: 10.5408964451,
447 quartiles
: (956.7500000000,970.5000000000,1078.7500000000),
453 fn test_norm10medium() {
466 let summ
= &Summary
{
467 sum
: 8653.0000000000,
469 max
: 1084.0000000000,
470 mean
: 865.3000000000,
471 median
: 911.5000000000,
472 var
: 48628.4555555556,
473 std_dev
: 220.5186059170,
474 std_dev_pct
: 25.4846418487,
475 median_abs_dev
: 195.7032000000,
476 median_abs_dev_pct
: 21.4704552935,
477 quartiles
: (771.0000000000,911.5000000000,1017.2500000000),
483 fn test_norm10wide() {
496 let summ
= &Summary
{
497 sum
: 9349.0000000000,
499 max
: 1591.0000000000,
500 mean
: 934.9000000000,
501 median
: 913.5000000000,
502 var
: 239208.9888888889,
503 std_dev
: 489.0899599142,
504 std_dev_pct
: 52.3146817750,
505 median_abs_dev
: 611.5725000000,
506 median_abs_dev_pct
: 66.9482758621,
507 quartiles
: (567.2500000000,913.5000000000,1331.2500000000),
513 fn test_norm25verynarrow() {
541 let summ
= &Summary
{
542 sum
: 24926.0000000000,
544 max
: 1040.0000000000,
545 mean
: 997.0400000000,
546 median
: 998.0000000000,
548 std_dev
: 19.8294393937,
549 std_dev_pct
: 1.9888308788,
550 median_abs_dev
: 22.2390000000,
551 median_abs_dev_pct
: 2.2283567134,
552 quartiles
: (983.0000000000,998.0000000000,1013.0000000000),
571 let summ
= &Summary
{
576 median
: 11.5000000000,
578 std_dev
: 16.9643416875,
579 std_dev_pct
: 101.5828843560,
580 median_abs_dev
: 13.3434000000,
581 median_abs_dev_pct
: 116.0295652174,
582 quartiles
: (4.2500000000,11.5000000000,22.5000000000),
601 let summ
= &Summary
{
606 median
: 24.5000000000,
608 std_dev
: 19.5848580967,
609 std_dev_pct
: 74.4671410520,
610 median_abs_dev
: 22.9803000000,
611 median_abs_dev_pct
: 93.7971428571,
612 quartiles
: (9.5000000000,24.5000000000,36.5000000000),
631 let summ
= &Summary
{
636 median
: 22.0000000000,
638 std_dev
: 21.4050876611,
639 std_dev_pct
: 88.4507754589,
640 median_abs_dev
: 21.4977000000,
641 median_abs_dev_pct
: 97.7168181818,
642 quartiles
: (7.7500000000,22.0000000000,35.0000000000),
676 let summ
= &Summary
{
681 median
: 19.0000000000,
683 std_dev
: 24.5161851301,
684 std_dev_pct
: 103.3565983562,
685 median_abs_dev
: 19.2738000000,
686 median_abs_dev_pct
: 101.4410526316,
687 quartiles
: (6.0000000000,19.0000000000,31.0000000000),
721 let summ
= &Summary
{
726 median
: 20.0000000000,
728 std_dev
: 4.5650848842,
729 std_dev_pct
: 22.2037202539,
730 median_abs_dev
: 5.9304000000,
731 median_abs_dev_pct
: 29.6520000000,
732 quartiles
: (17.0000000000,20.0000000000,24.0000000000),
738 fn test_pois25lambda30() {
766 let summ
= &Summary
{
771 median
: 32.0000000000,
773 std_dev
: 5.1568724372,
774 std_dev_pct
: 16.3814245145,
775 median_abs_dev
: 5.9304000000,
776 median_abs_dev_pct
: 18.5325000000,
777 quartiles
: (28.0000000000,32.0000000000,34.0000000000),
783 fn test_pois25lambda40() {
811 let summ
= &Summary
{
812 sum
: 1019.0000000000,
816 median
: 42.0000000000,
818 std_dev
: 5.8685603004,
819 std_dev_pct
: 14.3978417577,
820 median_abs_dev
: 5.9304000000,
821 median_abs_dev_pct
: 14.1200000000,
822 quartiles
: (37.0000000000,42.0000000000,45.0000000000),
828 fn test_pois25lambda50() {
856 let summ
= &Summary
{
857 sum
: 1235.0000000000,
861 median
: 50.0000000000,
863 std_dev
: 5.6273143387,
864 std_dev_pct
: 11.3913245723,
865 median_abs_dev
: 4.4478000000,
866 median_abs_dev_pct
: 8.8956000000,
867 quartiles
: (44.0000000000,50.0000000000,52.0000000000),
901 let summ
= &Summary
{
902 sum
: 1242.0000000000,
906 median
: 45.0000000000,
907 var
: 1015.6433333333,
908 std_dev
: 31.8691595957,
909 std_dev_pct
: 64.1488719719,
910 median_abs_dev
: 45.9606000000,
911 median_abs_dev_pct
: 102.1346666667,
912 quartiles
: (29.0000000000,45.0000000000,79.0000000000),
920 assert_eq
!([0.5f64, 3.2321f64, 1.5678f64].sum(), 5.2999);
923 fn test_sum_f64_between_ints_that_sum_to_0() {
924 assert_eq
!([1e30f64
, 1.2f64, -1e30f64
].sum(), 1.2);
934 pub fn sum_three_items(b
: &mut Bencher
) {
936 [1e20f64
, 1.5f64, -1e20f64
].sum();
940 pub fn sum_many_f64(b
: &mut Bencher
) {
941 let nums
= [-1e30f64
, 1e60
, 1e30
, 1.0, -1e60
];
942 let v
= (0..500).map(|i
| nums
[i
%5]).collect
::<Vec
<_
>>();