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 "api/numerics/samples_stats_counter.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 namespace webrtc {
22 namespace {
23
CreateStatsFilledWithIntsFrom1ToN(int n)24 SamplesStatsCounter CreateStatsFilledWithIntsFrom1ToN(int n) {
25 std::vector<double> data;
26 for (int i = 1; i <= n; i++) {
27 data.push_back(i);
28 }
29 absl::c_shuffle(data, std::mt19937(std::random_device()()));
30
31 SamplesStatsCounter stats;
32 for (double v : data) {
33 stats.AddSample(v);
34 }
35 return stats;
36 }
37
38 // Add n samples drawn from uniform distribution in [a;b].
CreateStatsFromUniformDistribution(int n,double a,double b)39 SamplesStatsCounter CreateStatsFromUniformDistribution(int n,
40 double a,
41 double b) {
42 std::mt19937 gen{std::random_device()()};
43 std::uniform_real_distribution<> dis(a, b);
44
45 SamplesStatsCounter stats;
46 for (int i = 1; i <= n; i++) {
47 stats.AddSample(dis(gen));
48 }
49 return stats;
50 }
51
52 class SamplesStatsCounterTest : public ::testing::TestWithParam<int> {};
53
54 constexpr int SIZE_FOR_MERGE = 10;
55
56 } // namespace
57
TEST(SamplesStatsCounterTest,FullSimpleTest)58 TEST(SamplesStatsCounterTest, FullSimpleTest) {
59 SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(100);
60
61 EXPECT_TRUE(!stats.IsEmpty());
62 EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
63 EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
64 EXPECT_NEAR(stats.GetAverage(), 50.5, 1e-6);
65 for (int i = 1; i <= 100; i++) {
66 double p = i / 100.0;
67 EXPECT_GE(stats.GetPercentile(p), i);
68 EXPECT_LT(stats.GetPercentile(p), i + 1);
69 }
70 }
71
TEST(SamplesStatsCounterTest,VarianceAndDeviation)72 TEST(SamplesStatsCounterTest, VarianceAndDeviation) {
73 SamplesStatsCounter stats;
74 stats.AddSample(2);
75 stats.AddSample(2);
76 stats.AddSample(-1);
77 stats.AddSample(5);
78
79 EXPECT_DOUBLE_EQ(stats.GetAverage(), 2.0);
80 EXPECT_DOUBLE_EQ(stats.GetVariance(), 4.5);
81 EXPECT_DOUBLE_EQ(stats.GetStandardDeviation(), sqrt(4.5));
82 }
83
TEST(SamplesStatsCounterTest,FractionPercentile)84 TEST(SamplesStatsCounterTest, FractionPercentile) {
85 SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
86
87 EXPECT_DOUBLE_EQ(stats.GetPercentile(0.5), 3);
88 }
89
TEST(SamplesStatsCounterTest,TestBorderValues)90 TEST(SamplesStatsCounterTest, TestBorderValues) {
91 SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
92
93 EXPECT_GE(stats.GetPercentile(0.01), 1);
94 EXPECT_LT(stats.GetPercentile(0.01), 2);
95 EXPECT_DOUBLE_EQ(stats.GetPercentile(1.0), 5);
96 }
97
TEST(SamplesStatsCounterTest,VarianceFromUniformDistribution)98 TEST(SamplesStatsCounterTest, VarianceFromUniformDistribution) {
99 // Check variance converge to 1/12 for [0;1) uniform distribution.
100 // Acts as a sanity check for NumericStabilityForVariance test.
101 SamplesStatsCounter stats = CreateStatsFromUniformDistribution(1e6, 0, 1);
102
103 EXPECT_NEAR(stats.GetVariance(), 1. / 12, 1e-3);
104 }
105
TEST(SamplesStatsCounterTest,NumericStabilityForVariance)106 TEST(SamplesStatsCounterTest, NumericStabilityForVariance) {
107 // Same test as VarianceFromUniformDistribution,
108 // except the range is shifted to [1e9;1e9+1).
109 // Variance should also converge to 1/12.
110 // NB: Although we lose precision for the samples themselves, the fractional
111 // part still enjoys 22 bits of mantissa and errors should even out,
112 // so that couldn't explain a mismatch.
113 SamplesStatsCounter stats =
114 CreateStatsFromUniformDistribution(1e6, 1e9, 1e9 + 1);
115
116 EXPECT_NEAR(stats.GetVariance(), 1. / 12, 1e-3);
117 }
118
TEST_P(SamplesStatsCounterTest,AddSamples)119 TEST_P(SamplesStatsCounterTest, AddSamples) {
120 int data[SIZE_FOR_MERGE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
121 // Split the data in different partitions.
122 // We have 11 distinct tests:
123 // * Empty merged with full sequence.
124 // * 1 sample merged with 9 last.
125 // * 2 samples merged with 8 last.
126 // [...]
127 // * Full merged with empty sequence.
128 // All must lead to the same result.
129 SamplesStatsCounter stats0, stats1;
130 for (int i = 0; i < GetParam(); ++i) {
131 stats0.AddSample(data[i]);
132 }
133 for (int i = GetParam(); i < SIZE_FOR_MERGE; ++i) {
134 stats1.AddSample(data[i]);
135 }
136 stats0.AddSamples(stats1);
137
138 EXPECT_EQ(stats0.GetMin(), 0);
139 EXPECT_EQ(stats0.GetMax(), 9);
140 EXPECT_DOUBLE_EQ(stats0.GetAverage(), 4.5);
141 EXPECT_DOUBLE_EQ(stats0.GetVariance(), 8.25);
142 EXPECT_DOUBLE_EQ(stats0.GetStandardDeviation(), sqrt(8.25));
143 EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.1), 0.9);
144 EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.5), 4.5);
145 EXPECT_DOUBLE_EQ(stats0.GetPercentile(0.9), 8.1);
146 }
147
TEST(SamplesStatsCounterTest,MultiplyRight)148 TEST(SamplesStatsCounterTest, MultiplyRight) {
149 SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(10);
150
151 EXPECT_TRUE(!stats.IsEmpty());
152 EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
153 EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
154 EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
155
156 SamplesStatsCounter multiplied_stats = stats * 10;
157 EXPECT_TRUE(!multiplied_stats.IsEmpty());
158 EXPECT_DOUBLE_EQ(multiplied_stats.GetMin(), 10.0);
159 EXPECT_DOUBLE_EQ(multiplied_stats.GetMax(), 100.0);
160 EXPECT_DOUBLE_EQ(multiplied_stats.GetAverage(), 55.0);
161 EXPECT_EQ(multiplied_stats.GetSamples().size(), stats.GetSamples().size());
162
163 // Check that origin stats were not modified.
164 EXPECT_TRUE(!stats.IsEmpty());
165 EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
166 EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
167 EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
168 }
169
TEST(SamplesStatsCounterTest,MultiplyLeft)170 TEST(SamplesStatsCounterTest, MultiplyLeft) {
171 SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(10);
172
173 EXPECT_TRUE(!stats.IsEmpty());
174 EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
175 EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
176 EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
177
178 SamplesStatsCounter multiplied_stats = 10 * stats;
179 EXPECT_TRUE(!multiplied_stats.IsEmpty());
180 EXPECT_DOUBLE_EQ(multiplied_stats.GetMin(), 10.0);
181 EXPECT_DOUBLE_EQ(multiplied_stats.GetMax(), 100.0);
182 EXPECT_DOUBLE_EQ(multiplied_stats.GetAverage(), 55.0);
183 EXPECT_EQ(multiplied_stats.GetSamples().size(), stats.GetSamples().size());
184
185 // Check that origin stats were not modified.
186 EXPECT_TRUE(!stats.IsEmpty());
187 EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
188 EXPECT_DOUBLE_EQ(stats.GetMax(), 10.0);
189 EXPECT_DOUBLE_EQ(stats.GetAverage(), 5.5);
190 }
191
TEST(SamplesStatsCounterTest,Divide)192 TEST(SamplesStatsCounterTest, Divide) {
193 SamplesStatsCounter stats;
194 for (int i = 1; i <= 10; i++) {
195 stats.AddSample(i * 10);
196 }
197
198 EXPECT_TRUE(!stats.IsEmpty());
199 EXPECT_DOUBLE_EQ(stats.GetMin(), 10.0);
200 EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
201 EXPECT_DOUBLE_EQ(stats.GetAverage(), 55.0);
202
203 SamplesStatsCounter divided_stats = stats / 10;
204 EXPECT_TRUE(!divided_stats.IsEmpty());
205 EXPECT_DOUBLE_EQ(divided_stats.GetMin(), 1.0);
206 EXPECT_DOUBLE_EQ(divided_stats.GetMax(), 10.0);
207 EXPECT_DOUBLE_EQ(divided_stats.GetAverage(), 5.5);
208 EXPECT_EQ(divided_stats.GetSamples().size(), stats.GetSamples().size());
209
210 // Check that origin stats were not modified.
211 EXPECT_TRUE(!stats.IsEmpty());
212 EXPECT_DOUBLE_EQ(stats.GetMin(), 10.0);
213 EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
214 EXPECT_DOUBLE_EQ(stats.GetAverage(), 55.0);
215 }
216
217 INSTANTIATE_TEST_SUITE_P(SamplesStatsCounterTests,
218 SamplesStatsCounterTest,
219 ::testing::Range(0, SIZE_FOR_MERGE + 1));
220
221 } // namespace webrtc
222