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 // http://arxiv.org/pdf/1407.1121v1.pdf. There are several parts to the | |
Charlie Harrison
2016/09/01 18:17:52
https url?
Randy Smith (Not in Mondays)
2016/09/18 19:12:35
Done.
| |
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. | |
Charlie Harrison
2016/09/01 18:17:53
I think you have this backwards. Let's go off of a
Randy Smith (Not in Mondays)
2016/09/18 19:12:35
Whoops!! Thank you for catching that. And I had
| |
29 // The estimate is only moved towards the sample if a random number between | |
30 // 0 and 1 falls on the side of the quantile the sample must be in to | |
31 // indicate that quantile must be adjusted. E.g. in the case of the 90%l | |
32 // estimation, the estimate would only move up in 10% of the cases in which | |
33 // the sample was above the estimate, but it would move down in 90% of the | |
34 // cases in which the sample was below the estimate. | |
35 // * Every time the estimate moves in the same direction, the step amount is | |
36 // increased by one, and every time the estimate reverses direction, the | |
37 // step amount is decreased (to 1, if greater than 1, by one, if zero or | |
38 // negative). The effective step amount is Max(step, 1). | |
39 // * If the estimate would be moved beyond the sample causing its move, | |
40 // it is moved to be equal to the same (and the step amount set to the | |
41 // distance to the sample). | |
42 // See the paper for further details. | |
43 | |
44 QuantileEstimator::QuantileEstimator(int quantile, int initial_estimate) | |
45 : quantile_(quantile), | |
46 sign_positive_(true), | |
47 current_estimate_(initial_estimate), | |
48 current_step_(1), | |
49 generator_callback_(base::Bind(&GenerateRand0To99)) {} | |
50 | |
51 QuantileEstimator::~QuantileEstimator() {} | |
52 | |
53 void QuantileEstimator::AddSample(int sample) { | |
54 int rand100 = generator_callback_.Run(); | |
55 if (sample > current_estimate_ && rand100 >= quantile_) { | |
56 current_step_ += sign_positive_ ? 1 : -1; | |
57 current_estimate_ += (current_step_ > 0) ? current_step_ : 1; | |
58 | |
59 // Clamp movement to distance to sample. | |
60 if (current_estimate_ > sample) { | |
61 current_step_ -= current_estimate_ - sample; | |
62 current_estimate_ = sample; | |
63 } | |
64 | |
65 // If we've reversed direction, reset the step down. | |
66 if (!sign_positive_ && current_step_ > 1) | |
67 current_step_ = 1; | |
68 | |
69 sign_positive_ = true; | |
70 } else if (sample < current_estimate_ && rand100 < quantile_) { | |
71 current_step_ += !sign_positive_ ? 1 : -1; | |
72 current_estimate_ -= (current_step_ > 0) ? current_step_ : 1; | |
73 | |
74 // Clamp movement to distance to sample. | |
75 if (current_estimate_ < sample) { | |
76 current_step_ -= sample - current_estimate_; | |
77 current_estimate_ = sample; | |
78 } | |
79 | |
80 // If we've reversed direction, reset the step down. | |
81 if (sign_positive_ && current_step_ > 1) | |
82 current_step_ = 1; | |
83 | |
84 sign_positive_ = false; | |
85 } | |
86 } | |
87 | |
88 void QuantileEstimator::SetRandomNumberGeneratorForTesting( | |
89 RandomNumberCallback generator_callback) { | |
90 generator_callback_ = generator_callback; | |
91 } | |
92 | |
93 } // namespace net | |
OLD | NEW |