metrics: Add RandomSelector, a class that randomly selects items with odds

chrome/browser/metrics/perf/random_selector.cc

Index: chrome/browser/metrics/perf/random_selector.cc
diff --git a/chrome/browser/metrics/perf/random_selector.cc b/chrome/browser/metrics/perf/random_selector.cc
new file mode 100644
index 0000000000000000000000000000000000000000..b6596b270c130b07dc3afb6771541254b893b816
--- /dev/null
+++ b/chrome/browser/metrics/perf/random_selector.cc
@@ -0,0 +1,59 @@
+// Copyright 2015 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 "chrome/browser/metrics/perf/random_selector.h"
+
+#include <string>
+#include <vector>
+
+#include "base/logging.h"
+#include "base/rand_util.h"
+#include "base/strings/string_number_conversions.h"
+#include "base/strings/string_split.h"
+#include "base/strings/string_util.h"
+
+namespace metrics {
+
+RandomSelector::RandomSelector() {}
+
+RandomSelector::~RandomSelector() {}
+
+double RandomSelector::SumOdds(const std::vector<OddsAndValue>& odds) {
+  double sum = 0.0;
+  for (const auto& odd : odds) {
+    sum += odd.weight;
+  }
+  return sum;
+}
+
+void RandomSelector::SetOdds(const std::vector<OddsAndValue>& odds) {
+  odds_ = odds;
+  sum_of_odds_ = SumOdds(odds_);
+}
+
+const std::string& RandomSelector::GetNext() {
+  // Get a random double between 0 and the sum.
+  double random = RandDoubleUpTo(sum_of_odds_);
+  // Figure out what it belongs to.
+  return GetKeyOf(random);
+}
+
+double RandomSelector::RandDoubleUpTo(double max) {
+  CHECK_GT(max, 0.0);
+  return max * base::RandDouble();
+}
+
+const std::string& RandomSelector::GetKeyOf(double value) {

[Alexei Svitkine (slow), 2015/09/14 19:12:33]

The name key in the function name is confusing, since you don't use that
terminology anywhere else.

In the struct, you name it value - so you can change the name to that term (and
rename to param to something else - or perhaps GetStringFor(double value).

[dhsharp, 2015/09/15 00:00:21]

Done.

+  double current = 0.0;
+  for (const auto& odd : odds_) {
+    current += odd.weight;
+    if (value < current) {

[Alexei Svitkine (slow), 2015/09/14 19:12:33]

Nit: No {}'s

[dhsharp, 2015/09/15 00:00:21]

Done.

+      return odd.value;
+    }
+  }
+  NOTREACHED() << "Invalid value for key: " << value;
+  return base::EmptyString();

[Alexei Svitkine (slow), 2015/09/14 19:12:33]

The comment on base::EmptyString() suggest that it's often better to just return
std::string().

If there's a good reason to use base::EmptyString() here instead, it should be
documented.

[dhsharp, 2015/09/15 00:00:21]

`return std::string()` would be returning a reference to an a temporary which is
about to go out of scope, which is undefined behavior, and results in a compiler
warning/error. Reading the doc of EmptyString, this is exactly what it is
intended for, despite the scary language around it. Does using this function as
intended really need to be specially explained?

[Alexei Svitkine (slow), 2015/09/15 15:31:18]

Gotcha. Fair enough.

+}
+
+}  // namespace metrics