Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 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 | |
Artem Titov | 9d77762 | 2020-09-18 16:23:08 | [diff] [blame] | 11 | #include "api/numerics/samples_stats_counter.h" |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 12 | |
Artem Titov | e6f6a0c | 2019-02-07 11:14:35 | [diff] [blame] | 13 | #include <math.h> |
Jonas Olsson | a4d8737 | 2019-07-05 17:08:33 | [diff] [blame] | 14 | |
Artem Titov | d2a6378 | 2019-03-21 09:37:37 | [diff] [blame] | 15 | #include <random> |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 16 | #include <vector> |
| 17 | |
Steve Anton | 2acd163 | 2019-03-25 20:48:30 | [diff] [blame] | 18 | #include "absl/algorithm/container.h" |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 19 | #include "test/gtest.h" |
| 20 | |
| 21 | namespace webrtc { |
| 22 | namespace { |
Artem Titov | e6f6a0c | 2019-02-07 11:14:35 | [diff] [blame] | 23 | |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 24 | SamplesStatsCounter CreateStatsFilledWithIntsFrom1ToN(int n) { |
| 25 | std::vector<double> data; |
| 26 | for (int i = 1; i <= n; i++) { |
| 27 | data.push_back(i); |
| 28 | } |
Steve Anton | 2acd163 | 2019-03-25 20:48:30 | [diff] [blame] | 29 | absl::c_shuffle(data, std::mt19937(std::random_device()())); |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 30 | |
| 31 | SamplesStatsCounter stats; |
| 32 | for (double v : data) { |
| 33 | stats.AddSample(v); |
| 34 | } |
| 35 | return stats; |
| 36 | } |
Artem Titov | e6f6a0c | 2019-02-07 11:14:35 | [diff] [blame] | 37 | |
Yves Gerey | 890f62b | 2019-04-10 15:18:48 | [diff] [blame] | 38 | // Add n samples drawn from uniform distribution in [a;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 | |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 56 | } // namespace |
| 57 | |
Artem Titov | 2c5af4f | 2019-07-03 08:40:16 | [diff] [blame] | 58 | TEST(SamplesStatsCounterTest, FullSimpleTest) { |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 59 | SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(100); |
| 60 | |
Artem Titov | e6f6a0c | 2019-02-07 11:14:35 | [diff] [blame] | 61 | EXPECT_TRUE(!stats.IsEmpty()); |
| 62 | EXPECT_DOUBLE_EQ(stats.GetMin(), 1.0); |
| 63 | EXPECT_DOUBLE_EQ(stats.GetMax(), 100.0); |
Artem Titov | b6b4dee | 2019-08-22 14:34:54 | [diff] [blame] | 64 | EXPECT_NEAR(stats.GetAverage(), 50.5, 1e-6); |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 65 | for (int i = 1; i <= 100; i++) { |
| 66 | double p = i / 100.0; |
Artem Titov | e6f6a0c | 2019-02-07 11:14:35 | [diff] [blame] | 67 | EXPECT_GE(stats.GetPercentile(p), i); |
| 68 | EXPECT_LT(stats.GetPercentile(p), i + 1); |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 69 | } |
| 70 | } |
| 71 | |
Artem Titov | 2c5af4f | 2019-07-03 08:40:16 | [diff] [blame] | 72 | TEST(SamplesStatsCounterTest, VarianceAndDeviation) { |
Artem Titov | e6f6a0c | 2019-02-07 11:14:35 | [diff] [blame] | 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 | |
Artem Titov | 2c5af4f | 2019-07-03 08:40:16 | [diff] [blame] | 84 | TEST(SamplesStatsCounterTest, FractionPercentile) { |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 85 | SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5); |
| 86 | |
Artem Titov | e6f6a0c | 2019-02-07 11:14:35 | [diff] [blame] | 87 | EXPECT_DOUBLE_EQ(stats.GetPercentile(0.5), 3); |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 88 | } |
| 89 | |
Artem Titov | 2c5af4f | 2019-07-03 08:40:16 | [diff] [blame] | 90 | TEST(SamplesStatsCounterTest, TestBorderValues) { |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 91 | SamplesStatsCounter stats = CreateStatsFilledWithIntsFrom1ToN(5); |
| 92 | |
Artem Titov | e6f6a0c | 2019-02-07 11:14:35 | [diff] [blame] | 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); |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 96 | } |
| 97 | |
Artem Titov | 2c5af4f | 2019-07-03 08:40:16 | [diff] [blame] | 98 | TEST(SamplesStatsCounterTest, VarianceFromUniformDistribution) { |
Yves Gerey | 890f62b | 2019-04-10 15:18:48 | [diff] [blame] | 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 | |
Artem Titov | 2c5af4f | 2019-07-03 08:40:16 | [diff] [blame] | 106 | TEST(SamplesStatsCounterTest, NumericStabilityForVariance) { |
Yves Gerey | 890f62b | 2019-04-10 15:18:48 | [diff] [blame] | 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 | |
| 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 | |
Artem Titov | 2c5af4f | 2019-07-03 08:40:16 | [diff] [blame] | 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 | |
| 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 | |
| 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 | |
Yves Gerey | 890f62b | 2019-04-10 15:18:48 | [diff] [blame] | 217 | INSTANTIATE_TEST_SUITE_P(SamplesStatsCounterTests, |
| 218 | SamplesStatsCounterTest, |
| 219 | ::testing::Range(0, SIZE_FOR_MERGE + 1)); |
| 220 | |
Artem Titov | e4ed6ea | 2019-01-11 10:02:19 | [diff] [blame] | 221 | } // namespace webrtc |