1 /*
2 * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "rtc_base/numerics/running_statistics.h"
12
13 #include <math.h>
14
15 #include <random>
16 #include <vector>
17
18 #include "absl/algorithm/container.h"
19 #include "test/gtest.h"
20
21 // Tests were copied from samples_stats_counter_unittest.cc.
22
23 namespace webrtc {
24 namespace webrtc_impl {
25 namespace {
26
CreateStatsFilledWithIntsFrom1ToN(int n)27 RunningStatistics<double> CreateStatsFilledWithIntsFrom1ToN(int n) {
28 std::vector<double> data;
29 for (int i = 1; i <= n; i++) {
30 data.push_back(i);
31 }
32 absl::c_shuffle(data, std::mt19937(std::random_device()()));
33
34 RunningStatistics<double> stats;
35 for (double v : data) {
36 stats.AddSample(v);
37 }
38 return stats;
39 }
40
41 // Add n samples drawn from uniform distribution in [a;b].
CreateStatsFromUniformDistribution(int n,double a,double b)42 RunningStatistics<double> CreateStatsFromUniformDistribution(int n,
43 double a,
44 double b) {
45 std::mt19937 gen{std::random_device()()};
46 std::uniform_real_distribution<> dis(a, b);
47
48 RunningStatistics<double> stats;
49 for (int i = 1; i <= n; i++) {
50 stats.AddSample(dis(gen));
51 }
52 return stats;
53 }
54
55 class RunningStatisticsTest : public ::testing::TestWithParam<int> {};
56
57 constexpr int SIZE_FOR_MERGE = 5;
58
TEST(RunningStatistics,FullSimpleTest)59 TEST(RunningStatistics, FullSimpleTest) {
60 auto stats = CreateStatsFilledWithIntsFrom1ToN(100);
61
62 EXPECT_DOUBLE_EQ(*stats.GetMin(), 1.0);
63 EXPECT_DOUBLE_EQ(*stats.GetMax(), 100.0);
64 // EXPECT_DOUBLE_EQ is too strict (max 4 ULP) for this one.
65 ASSERT_NEAR(*stats.GetMean(), 50.5, 1e-10);
66 }
67
TEST(RunningStatistics,VarianceAndDeviation)68 TEST(RunningStatistics, VarianceAndDeviation) {
69 RunningStatistics<int> stats;
70 stats.AddSample(2);
71 stats.AddSample(2);
72 stats.AddSample(-1);
73 stats.AddSample(5);
74
75 EXPECT_DOUBLE_EQ(*stats.GetMean(), 2.0);
76 EXPECT_DOUBLE_EQ(*stats.GetVariance(), 4.5);
77 EXPECT_DOUBLE_EQ(*stats.GetStandardDeviation(), sqrt(4.5));
78 }
79
TEST(RunningStatistics,RemoveSample)80 TEST(RunningStatistics, RemoveSample) {
81 // We check that adding then removing sample is no-op,
82 // or so (due to loss of precision).
83 RunningStatistics<int> stats;
84 stats.AddSample(2);
85 stats.AddSample(2);
86 stats.AddSample(-1);
87 stats.AddSample(5);
88
89 constexpr int iterations = 1e5;
90 for (int i = 0; i < iterations; ++i) {
91 stats.AddSample(i);
92 stats.RemoveSample(i);
93
94 EXPECT_NEAR(*stats.GetMean(), 2.0, 1e-8);
95 EXPECT_NEAR(*stats.GetVariance(), 4.5, 1e-3);
96 EXPECT_NEAR(*stats.GetStandardDeviation(), sqrt(4.5), 1e-4);
97 }
98 }
99
TEST(RunningStatistics,RemoveSamplesSequence)100 TEST(RunningStatistics, RemoveSamplesSequence) {
101 // We check that adding then removing a sequence of samples is no-op,
102 // or so (due to loss of precision).
103 RunningStatistics<int> stats;
104 stats.AddSample(2);
105 stats.AddSample(2);
106 stats.AddSample(-1);
107 stats.AddSample(5);
108
109 constexpr int iterations = 1e4;
110 for (int i = 0; i < iterations; ++i) {
111 stats.AddSample(i);
112 }
113 for (int i = 0; i < iterations; ++i) {
114 stats.RemoveSample(i);
115 }
116
117 EXPECT_NEAR(*stats.GetMean(), 2.0, 1e-7);
118 EXPECT_NEAR(*stats.GetVariance(), 4.5, 1e-3);
119 EXPECT_NEAR(*stats.GetStandardDeviation(), sqrt(4.5), 1e-4);
120 }
121
TEST(RunningStatistics,VarianceFromUniformDistribution)122 TEST(RunningStatistics, VarianceFromUniformDistribution) {
123 // Check variance converge to 1/12 for [0;1) uniform distribution.
124 // Acts as a sanity check for NumericStabilityForVariance test.
125 auto stats = CreateStatsFromUniformDistribution(1e6, 0, 1);
126
127 EXPECT_NEAR(*stats.GetVariance(), 1. / 12, 1e-3);
128 }
129
TEST(RunningStatistics,NumericStabilityForVariance)130 TEST(RunningStatistics, NumericStabilityForVariance) {
131 // Same test as VarianceFromUniformDistribution,
132 // except the range is shifted to [1e9;1e9+1).
133 // Variance should also converge to 1/12.
134 // NB: Although we lose precision for the samples themselves, the fractional
135 // part still enjoys 22 bits of mantissa and errors should even out,
136 // so that couldn't explain a mismatch.
137 auto stats = CreateStatsFromUniformDistribution(1e6, 1e9, 1e9 + 1);
138
139 EXPECT_NEAR(*stats.GetVariance(), 1. / 12, 1e-3);
140 }
141
TEST(RunningStatistics,MinRemainsUnchangedAfterRemove)142 TEST(RunningStatistics, MinRemainsUnchangedAfterRemove) {
143 // We don't want to recompute min (that's RollingAccumulator's role),
144 // check we get the overall min.
145 RunningStatistics<int> stats;
146 stats.AddSample(1);
147 stats.AddSample(2);
148 stats.RemoveSample(1);
149 EXPECT_EQ(stats.GetMin(), 1);
150 }
151
TEST(RunningStatistics,MaxRemainsUnchangedAfterRemove)152 TEST(RunningStatistics, MaxRemainsUnchangedAfterRemove) {
153 // We don't want to recompute max (that's RollingAccumulator's role),
154 // check we get the overall max.
155 RunningStatistics<int> stats;
156 stats.AddSample(1);
157 stats.AddSample(2);
158 stats.RemoveSample(2);
159 EXPECT_EQ(stats.GetMax(), 2);
160 }
161
TEST_P(RunningStatisticsTest,MergeStatistics)162 TEST_P(RunningStatisticsTest, MergeStatistics) {
163 int data[SIZE_FOR_MERGE] = {2, 2, -1, 5, 10};
164 // Split the data in different partitions.
165 // We have 6 distinct tests:
166 // * Empty merged with full sequence.
167 // * 1 sample merged with 4 last.
168 // * 2 samples merged with 3 last.
169 // [...]
170 // * Full merged with empty sequence.
171 // All must lead to the same result.
172 // I miss QuickCheck so much.
173 RunningStatistics<int> stats0, stats1;
174 for (int i = 0; i < GetParam(); ++i) {
175 stats0.AddSample(data[i]);
176 }
177 for (int i = GetParam(); i < SIZE_FOR_MERGE; ++i) {
178 stats1.AddSample(data[i]);
179 }
180 stats0.MergeStatistics(stats1);
181
182 EXPECT_EQ(stats0.Size(), SIZE_FOR_MERGE);
183 EXPECT_DOUBLE_EQ(*stats0.GetMin(), -1);
184 EXPECT_DOUBLE_EQ(*stats0.GetMax(), 10);
185 EXPECT_DOUBLE_EQ(*stats0.GetMean(), 3.6);
186 EXPECT_DOUBLE_EQ(*stats0.GetVariance(), 13.84);
187 EXPECT_DOUBLE_EQ(*stats0.GetStandardDeviation(), sqrt(13.84));
188 }
189
190 INSTANTIATE_TEST_SUITE_P(RunningStatisticsTests,
191 RunningStatisticsTest,
192 ::testing::Range(0, SIZE_FOR_MERGE + 1));
193
194 } // namespace
195 } // namespace webrtc_impl
196 } // namespace webrtc
197