Index: net/base/quantile_estimator.cc |
diff --git a/net/base/quantile_estimator.cc b/net/base/quantile_estimator.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..b4ed7e2d1839a81760577dc6be81a454f8c5bd85 |
--- /dev/null |
+++ b/net/base/quantile_estimator.cc |
@@ -0,0 +1,93 @@ |
+// Copyright 2016 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "quantile_estimator.h" |
+ |
+#include "base/bind.h" |
+#include "base/callback.h" |
+#include "base/rand_util.h" |
+ |
+namespace { |
+ |
+// Random number wrapper to allow substitutions for testing. |
+int GenerateRand0To99() { |
+ return base::RandInt(0, 99); |
+} |
+ |
+} // namespace |
+ |
+namespace net { |
+ |
+// The algorithm used for quantile estimation is "Algorithm 3" from |
+// 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.
|
+// algorithm: |
+// * The estimate is conditionally moved towards the sample by a step amount. |
+// This means that if the samples are clustered around a value the estimates |
+// will converge to that sample. |
+// * 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
|
+// The estimate is only moved towards the sample if a random number between |
+// 0 and 1 falls on the side of the quantile the sample must be in to |
+// indicate that quantile must be adjusted. E.g. in the case of the 90%l |
+// estimation, the estimate would only move up in 10% of the cases in which |
+// the sample was above the estimate, but it would move down in 90% of the |
+// cases in which the sample was below the estimate. |
+// * Every time the estimate moves in the same direction, the step amount is |
+// increased by one, and every time the estimate reverses direction, the |
+// step amount is decreased (to 1, if greater than 1, by one, if zero or |
+// negative). The effective step amount is Max(step, 1). |
+// * If the estimate would be moved beyond the sample causing its move, |
+// it is moved to be equal to the same (and the step amount set to the |
+// distance to the sample). |
+// See the paper for further details. |
+ |
+QuantileEstimator::QuantileEstimator(int quantile, int initial_estimate) |
+ : quantile_(quantile), |
+ sign_positive_(true), |
+ current_estimate_(initial_estimate), |
+ current_step_(1), |
+ generator_callback_(base::Bind(&GenerateRand0To99)) {} |
+ |
+QuantileEstimator::~QuantileEstimator() {} |
+ |
+void QuantileEstimator::AddSample(int sample) { |
+ int rand100 = generator_callback_.Run(); |
+ if (sample > current_estimate_ && rand100 >= quantile_) { |
+ current_step_ += sign_positive_ ? 1 : -1; |
+ current_estimate_ += (current_step_ > 0) ? current_step_ : 1; |
+ |
+ // Clamp movement to distance to sample. |
+ if (current_estimate_ > sample) { |
+ current_step_ -= current_estimate_ - sample; |
+ current_estimate_ = sample; |
+ } |
+ |
+ // If we've reversed direction, reset the step down. |
+ if (!sign_positive_ && current_step_ > 1) |
+ current_step_ = 1; |
+ |
+ sign_positive_ = true; |
+ } else if (sample < current_estimate_ && rand100 < quantile_) { |
+ current_step_ += !sign_positive_ ? 1 : -1; |
+ current_estimate_ -= (current_step_ > 0) ? current_step_ : 1; |
+ |
+ // Clamp movement to distance to sample. |
+ if (current_estimate_ < sample) { |
+ current_step_ -= sample - current_estimate_; |
+ current_estimate_ = sample; |
+ } |
+ |
+ // If we've reversed direction, reset the step down. |
+ if (sign_positive_ && current_step_ > 1) |
+ current_step_ = 1; |
+ |
+ sign_positive_ = false; |
+ } |
+} |
+ |
+void QuantileEstimator::SetRandomNumberGeneratorForTesting( |
+ RandomNumberCallback generator_callback) { |
+ generator_callback_ = generator_callback; |
+} |
+ |
+} // namespace net |