blob: 1f9cabfb29df4f220bb765f4f15f68b2b061dc4b [file] [log] [blame]
Artem Titove4ed6ea2019-01-11 10:02:191/*
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
Artem Titov9d777622020-09-18 16:23:0811#include "api/numerics/samples_stats_counter.h"
Artem Titove4ed6ea2019-01-11 10:02:1912
Artem Titove6f6a0c2019-02-07 11:14:3513#include <math.h>
Jonas Olssona4d87372019-07-05 17:08:3314
Artem Titovd2a63782019-03-21 09:37:3715#include <random>
Artem Titove4ed6ea2019-01-11 10:02:1916#include <vector>
17
Steve Anton2acd1632019-03-25 20:48:3018#include "absl/algorithm/container.h"
Artem Titove4ed6ea2019-01-11 10:02:1919#include "test/gtest.h"
20
21namespace webrtc {
22namespace {
Artem Titove6f6a0c2019-02-07 11:14:3523
Artem Titove4ed6ea2019-01-11 10:02:1924SamplesStatsCounter CreateStatsFilledWithIntsFrom1ToN(int n) {
25 std::vector<double> data;
26 for (int i = 1; i <= n; i++) {
27 data.push_back(i);
28 }
Steve Anton2acd1632019-03-25 20:48:3029 absl::c_shuffle(data, std::mt19937(std::random_device()()));
Artem Titove4ed6ea2019-01-11 10:02:1930
31 SamplesStatsCounter stats;
32 for (double v : data) {
33 stats.AddSample(v);
34 }
35 return stats;
36}
Artem Titove6f6a0c2019-02-07 11:14:3537
Yves Gerey890f62b2019-04-10 15:18:4838// Add n samples drawn from uniform distribution in [a;b].
39SamplesStatsCounter 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
52class SamplesStatsCounterTest : public ::testing::TestWithParam<int> {};
53
54constexpr int SIZE_FOR_MERGE = 10;
55
Artem Titove4ed6ea2019-01-11 10:02:1956} // namespace
57
Artem Titov2c5af4f2019-07-03 08:40:1658TEST(SamplesStatsCounterTest, FullSimpleTest) {
Artem Titove4ed6ea2019-01-11 10:02:1959 SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(100);
60
Artem Titove6f6a0c2019-02-07 11:14:3561 EXPECT_TRUE(!stats.IsEmpty());
62 EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0);
63 EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0);
Artem Titovb6b4dee2019-08-22 14:34:5464 EXPECT_NEAR(stats.GetAverage(), 50.5, 1e-6);
Artem Titove4ed6ea2019-01-11 10:02:1965 for (int i = 1; i <= 100; i++) {
66 double p = i / 100.0;
Artem Titove6f6a0c2019-02-07 11:14:3567 EXPECT_GE(stats.GetPercentile(p), i);
68 EXPECT_LT(stats.GetPercentile(p), i + 1);
Artem Titove4ed6ea2019-01-11 10:02:1969 }
70}
71
Artem Titov2c5af4f2019-07-03 08:40:1672TEST(SamplesStatsCounterTest, VarianceAndDeviation) {
Artem Titove6f6a0c2019-02-07 11:14:3573 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
Artem Titov2c5af4f2019-07-03 08:40:1684TEST(SamplesStatsCounterTest, FractionPercentile) {
Artem Titove4ed6ea2019-01-11 10:02:1985 SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
86
Artem Titove6f6a0c2019-02-07 11:14:3587 EXPECT_DOUBLE_EQ(stats.GetPercentile(0.5), 3);
Artem Titove4ed6ea2019-01-11 10:02:1988}
89
Artem Titov2c5af4f2019-07-03 08:40:1690TEST(SamplesStatsCounterTest, TestBorderValues) {
Artem Titove4ed6ea2019-01-11 10:02:1991 SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5);
92
Artem Titove6f6a0c2019-02-07 11:14:3593 EXPECT_GE(stats.GetPercentile(0.01), 1);
94 EXPECT_LT(stats.GetPercentile(0.01), 2);
95 EXPECT_DOUBLE_EQ(stats.GetPercentile(1.0), 5);
Artem Titove4ed6ea2019-01-11 10:02:1996}
97
Artem Titov2c5af4f2019-07-03 08:40:1698TEST(SamplesStatsCounterTest, VarianceFromUniformDistribution) {
Yves Gerey890f62b2019-04-10 15:18:4899 // 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
Artem Titov2c5af4f2019-07-03 08:40:16106TEST(SamplesStatsCounterTest, NumericStabilityForVariance) {
Yves Gerey890f62b2019-04-10 15:18:48107 // 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
119TEST_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
Artem Titov2c5af4f2019-07-03 08:40:16148TEST(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
170TEST(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
192TEST(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
Yves Gerey890f62b2019-04-10 15:18:48217INSTANTIATE_TEST_SUITE_P(SamplesStatsCounterTests,
218 SamplesStatsCounterTest,
219 ::testing::Range(0, SIZE_FOR_MERGE + 1));
220
Artem Titove4ed6ea2019-01-11 10:02:19221} // namespace webrtc