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 "percentile_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 percentile 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 percentile requested (e.g. 90%l) is handled by the conditional move. |
| 29 // If the estimate is accurate, there is a chance equal to the percentile |
| 30 // value that a sample will be lower than it, and a chance equal to |
| 31 // 1-percentile that it will be higher. So the code balances those |
| 32 // probabilities by increasing the estimate in the percentile fraction |
| 33 // of the cases where the sample is over the estimate, and decreases the |
| 34 // estimate in (1-percentile) 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 PercentileEstimator::PercentileEstimator(int percentile, int initial_estimate) |
| 52 : percentile_(percentile), |
| 53 sign_positive_(true), |
| 54 current_estimate_(initial_estimate), |
| 55 current_step_(1), |
| 56 generator_callback_(base::Bind(&GenerateRand0To99)) {} |
| 57 |
| 58 PercentileEstimator::~PercentileEstimator() {} |
| 59 |
| 60 void PercentileEstimator::AddSample(int sample) { |
| 61 int rand100 = generator_callback_.Run(); |
| 62 if (sample > current_estimate_ && rand100 > 1 - percentile_) { |
| 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 > percentile_) { |
| 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 PercentileEstimator::SetRandomNumberGeneratorForTesting( |
| 96 RandomNumberCallback generator_callback) { |
| 97 generator_callback_ = generator_callback; |
| 98 } |
| 99 |
| 100 } // namespace net |
OLD | NEW |