OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #include "quantile_estimator.h" | |
6 | |
7 #include "base/bind.h" | |
8 #include "base/callback.h" | |
9 #include "base/rand_util.h" | |
10 | |
11 namespace { | |
12 | |
13 // Random number wrapper to allow substitutions for testing. | |
14 int GenerateRand0To99() { | |
15 return base::RandInt(0, 99); | |
16 } | |
17 | |
18 } // namespace | |
19 | |
20 namespace net { | |
21 | |
22 // The algorithm used for quantile estimation is "Algorithm 3" from | |
23 // https://arxiv.org/pdf/1407.1121v1.pdf. There are several parts to the | |
24 // algorithm: | |
25 // * The estimate is conditionally moved towards the sample by a step amount. | |
26 // This means that if the samples are clustered around a value the estimates | |
27 // will converge to that sample. | |
28 // * The quantile requested (e.g. 90%l) is handled by the conditional move. | |
29 // If the estimate is accurate, there is a chance equal to the quantile | |
30 // value that a sample will be lower than it, and a chance equal to | |
31 // 1-quantile that it will be higher. So the code balances those | |
32 // probabilities by increasing the estimate in the quantile fraction | |
33 // of the cases where the sample is over the estimate, and decreases the | |
34 // estimate in (1-quantile) fraction of the cases where the sample is under | |
35 // the estimate. | |
36 // E.g. in the case of the 90%l estimation, the estimate would | |
37 // move up in 90% of the cases in which the sample was above the | |
38 // estimate (which would be 10% of the total samples, presuming the | |
39 // estimate was accurate), and it would move down in 10% of the cases | |
40 // in which the sample was below the estimate. | |
41 // * Every time the estimate moves in the same direction, the step | |
42 // amount is increased by one, and every time the estimate reverses | |
43 // direction, the step amount is decreased (to 1, if greater than 1, | |
44 // by one, if zero or negative). The effective step amount is | |
45 // Max(step, 1). | |
46 // * If the estimate | |
47 // would be moved beyond the sample causing its move, it is moved to | |
48 // be equal to the same (and the step amount set to the distance to | |
49 // the sample). See the paper for further details. | |
50 | |
51 QuantileEstimator::QuantileEstimator(int quantile, int initial_estimate) | |
52 : quantile_(quantile), | |
53 sign_positive_(true), | |
54 current_estimate_(initial_estimate), | |
55 current_step_(1), | |
56 generator_callback_(base::Bind(&GenerateRand0To99)) {} | |
57 | |
58 QuantileEstimator::~QuantileEstimator() {} | |
59 | |
60 void QuantileEstimator::AddSample(int sample) { | |
61 int rand100 = generator_callback_.Run(); | |
62 if (sample > current_estimate_ && rand100 <= quantile_) { | |
Charlie Harrison
2016/09/19 16:35:36
optional nit: rand100 > 1 - quantile_ to align wit
Randy Smith (Not in Mondays)
2016/09/22 21:52:27
Done.
| |
63 current_step_ += sign_positive_ ? 1 : -1; | |
64 current_estimate_ += (current_step_ > 0) ? current_step_ : 1; | |
65 | |
66 // Clamp movement to distance to sample. | |
67 if (current_estimate_ > sample) { | |
68 current_step_ -= current_estimate_ - sample; | |
69 current_estimate_ = sample; | |
70 } | |
71 | |
72 // If we've reversed direction, reset the step down. | |
73 if (!sign_positive_ && current_step_ > 1) | |
74 current_step_ = 1; | |
75 | |
76 sign_positive_ = true; | |
77 } else if (sample < current_estimate_ && rand100 > quantile_) { | |
78 current_step_ += !sign_positive_ ? 1 : -1; | |
79 current_estimate_ -= (current_step_ > 0) ? current_step_ : 1; | |
80 | |
81 // Clamp movement to distance to sample. | |
82 if (current_estimate_ < sample) { | |
83 current_step_ -= sample - current_estimate_; | |
84 current_estimate_ = sample; | |
85 } | |
86 | |
87 // If we've reversed direction, reset the step down. | |
88 if (sign_positive_ && current_step_ > 1) | |
89 current_step_ = 1; | |
90 | |
91 sign_positive_ = false; | |
92 } | |
93 } | |
94 | |
95 void QuantileEstimator::SetRandomNumberGeneratorForTesting( | |
96 RandomNumberCallback generator_callback) { | |
97 generator_callback_ = generator_callback; | |
98 } | |
99 | |
100 } // namespace net | |
OLD | NEW |