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

This class was originally added to debugd in ChromeOS to select perf
command lines for CWP. That command selection is being moved up into
Chrome, so this class needs to be moved here. It will be used by
PerfProvider for the same purpose.

Review URL: https://codereview.chromium.org/1334943003

Cr-Commit-Position: refs/heads/master@{#349298}

5 files changed, 239 insertions, 0 deletions

diff --git a/chrome/browser/metrics/perf/random_selector.cc b/chrome/browser/metrics/perf/random_selector.cc
new file mode 100644
index 0000000..e32c8a0
--- /dev/null
+++ b/chrome/browser/metrics/perf/random_selector.cc
@@ -0,0 +1,51 @@
+// 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 "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"
+
+RandomSelector::RandomSelector() : sum_of_weights_(0) {}
+
+RandomSelector::~RandomSelector() {}
+
+double RandomSelector::SumWeights(const std::vector<WeightAndValue>& odds) {
+  double sum = 0.0;
+  for (const auto& odd : odds) {
+    sum += odd.weight;
+  }
+  return sum;
+}
+
+void RandomSelector::SetOdds(const std::vector<WeightAndValue>& odds) {
+  odds_ = odds;
+  sum_of_weights_ = SumWeights(odds_);
+}
+
+const std::string& RandomSelector::Select() {
+  // Get a random double between 0 and the sum.
+  double random = RandDoubleUpTo(sum_of_weights_);
+  // Figure out what it belongs to.
+  return GetValueFor(random);
+}
+
+double RandomSelector::RandDoubleUpTo(double max) {
+  CHECK_GT(max, 0.0);
+  return max * base::RandDouble();
+}
+
+const std::string& RandomSelector::GetValueFor(double random) {
+  double current = 0.0;
+  for (const auto& odd : odds_) {
+    current += odd.weight;
+    if (random < current)
+      return odd.value;
+  }
+  NOTREACHED() << "Invalid value for key: " << random;
+  return base::EmptyString();
+}
diff --git a/chrome/browser/metrics/perf/random_selector.h b/chrome/browser/metrics/perf/random_selector.h
new file mode 100644
index 0000000..4500525
--- /dev/null
+++ b/chrome/browser/metrics/perf/random_selector.h
@@ -0,0 +1,79 @@
+// 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.
+
+#ifndef CHROME_BROWSER_METRICS_PERF_RANDOM_SELECTOR_H_
+#define CHROME_BROWSER_METRICS_PERF_RANDOM_SELECTOR_H_
+
+#include <string>
+#include <vector>
+
+#include "base/macros.h"
+
+// RandomSelector can be used to pick vectors of strings according to certain
+// probabilities. The probabilities are set using SetOdds(). A randomly picked
+// vector can be obtained by calling Select().
+//
+// Sample usage:
+//
+// RandomSelector random_selector;
+// std::vector<RandomSelector::WeightAndValue> odds {
+//   {50, "a"},
+//   {40, "b"},
+//   {10, "c"}
+// };
+// random_selector.SetOdds(odds);
+//
+// std::vector<std::string>& selection = random_selector.Select();
+//
+// The above line should return "a" with a probability of 50%,
+// "b" with a probability of 40%, and "c" with a probability of 10%:
+class RandomSelector {
+ public:
+  struct WeightAndValue {
+    WeightAndValue(double weight, const std::string& value)
+      : weight(weight), value(value) {
+    }
+
+    // Probability weight for selecting this value.
+    double weight;
+    // Value to be returned by Select(), if selected.
+    std::string value;
+  };
+
+  RandomSelector();
+  virtual ~RandomSelector();
+
+  // Set the probabilities for various strings.
+  void SetOdds(const std::vector<WeightAndValue>& odds);
+
+  // Randomly select one of the values from the set.
+  const std::string& Select();
+
+  // Returns the number of string entries.
+  size_t num_values() const {
+    return odds_.size();
+  }
+
+  // Sum of the |weight| fields in the vector.
+  static double SumWeights(const std::vector<WeightAndValue>& odds);
+
+ private:
+  // Get a floating point number between 0.0 and |max|.
+  virtual double RandDoubleUpTo(double max);
+
+  // Get a string corresponding to |random| that is in the odds vector.
+  // |random| must be a number between zero and the sum of the probability
+  // weights.
+  const std::string& GetValueFor(double random);
+
+  // A dictionary representing the strings to choose from and associated odds.
+  std::vector<WeightAndValue> odds_;
+
+  // Sum of the probability weights.
+  double sum_of_weights_;
+
+  DISALLOW_COPY_AND_ASSIGN(RandomSelector);
+};
+
+#endif  // CHROME_BROWSER_METRICS_PERF_RANDOM_SELECTOR_H_
diff --git a/chrome/browser/metrics/perf/random_selector_unittest.cc b/chrome/browser/metrics/perf/random_selector_unittest.cc
new file mode 100644
index 0000000..d88a032
--- /dev/null
+++ b/chrome/browser/metrics/perf/random_selector_unittest.cc
@@ -0,0 +1,106 @@
+// 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 <cmath>
+#include <map>
+#include <string>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+// A small floating point number used to verify that the expected odds are equal
+// to the odds set.
+const double kEpsilon = 0.01;
+
+// A class that overrides RandDoubleUpTo() to not be random. The number
+// generator will emulate a uniform distribution of numbers between 0.0 and
+// |max| when called with the same |max| parameter and a whole multiple of
+// |random_period| times. This allows better testing of the RandomSelector
+// class.
+class RandomSelectorWithCustomRNG : public RandomSelector {
+ public:
+  explicit RandomSelectorWithCustomRNG(unsigned int random_period)
+      : random_period_(random_period), current_index_(0) {}
+
+ private:
+  // This function returns floats between 0.0 and |max| in an increasing
+  // fashion at regular intervals.
+  double RandDoubleUpTo(double max) override {
+    current_index_ = (current_index_ + 1) % random_period_;
+    return max * current_index_ / random_period_;
+  }
+
+  // Period (number of calls) over which the fake RNG repeats.
+  const unsigned int random_period_;
+
+  // Stores the current position we are at in the interval between 0.0 and
+  // |max|. See the function RandDoubleUpTo for details on how this is used.
+  int current_index_;
+
+  DISALLOW_COPY_AND_ASSIGN(RandomSelectorWithCustomRNG);
+};
+
+// Use the random_selector to generate some values. The number of values to
+// generate is |iterations|.
+void GenerateResults(size_t iterations,
+                     RandomSelector* random_selector,
+                     std::map<std::string, int>* results) {
+  for (size_t i = 0; i < iterations; ++i) {
+    const std::string& next_value = random_selector->Select();
+    (*results)[next_value]++;
+  }
+}
+
+// This function tests whether the results are close enough to the odds (within
+// 1%).
+void CheckResultsAgainstOdds(
+    const std::vector<RandomSelector::WeightAndValue>& odds,
+    const std::map<std::string, int>& results) {
+  EXPECT_EQ(odds.size(), results.size());
+
+  const double odds_sum = RandomSelector::SumWeights(odds);
+  int results_sum = 0;
+  for (const auto& item : results) {
+    results_sum += item.second;
+  }
+
+  for (const auto& odd : odds) {
+    const auto result = results.find(odd.value);
+    EXPECT_NE(result, results.end());
+    const double results_ratio = 1.0*result->second / results_sum;
+    const double odds_ratio = odd.weight / odds_sum;
+    const double abs_diff = std::abs(results_ratio - odds_ratio);
+    EXPECT_LT(abs_diff, kEpsilon);
+  }
+}
+
+TEST(RandomSelector, SimpleAccessors) {
+  using WeightAndValue = RandomSelector::WeightAndValue;
+  std::vector<WeightAndValue> odds;
+  odds.push_back(WeightAndValue(1, "a 1"));
+  odds.push_back(WeightAndValue(3, "b --help"));
+  odds.push_back(WeightAndValue(107, "c bar"));
+  EXPECT_EQ(111.0L, RandomSelector::SumWeights(odds));
+  RandomSelector random_selector;
+  random_selector.SetOdds(odds);
+  EXPECT_EQ(3UL, random_selector.num_values());
+}
+
+// Ensure RandomSelector is able to generate results from given odds.
+TEST(RandomSelector, GenerateTest) {
+  using WeightAndValue = RandomSelector::WeightAndValue;
+  const int kLargeNumber = 2000;
+  std::vector<RandomSelector::WeightAndValue> odds;
+  odds.push_back(WeightAndValue(1, "a 1"));
+  odds.push_back(WeightAndValue(2, "b --help"));
+  odds.push_back(WeightAndValue(3, "c bar"));
+  RandomSelectorWithCustomRNG random_selector(kLargeNumber);
+  random_selector.SetOdds(odds);
+  // Generate a lot of values.
+  std::map<std::string, int> results;
+  GenerateResults(kLargeNumber, &random_selector, &results);
+  // Ensure the values and odds are related.
+  CheckResultsAgainstOdds(odds, results);
+}
diff --git a/chrome/chrome_browser.gypi b/chrome/chrome_browser.gypi
index 719f521..fb24e8d 100644
--- a/chrome/chrome_browser.gypi
+++ b/chrome/chrome_browser.gypi
@@ -924,6 +924,8 @@
       'browser/media/protected_media_identifier_permission_context_factory.h',
       'browser/metrics/chromeos_metrics_provider.cc',
       'browser/metrics/chromeos_metrics_provider.h',
+      'browser/metrics/perf/random_selector.cc',
+      'browser/metrics/perf/random_selector.h',
       'browser/metrics/perf/windowed_incognito_observer.cc',
       'browser/metrics/perf/windowed_incognito_observer.h',
       # This is technically also dependent on enable_plugins but we don't
diff --git a/chrome/chrome_tests_unit.gypi b/chrome/chrome_tests_unit.gypi
index 4a6c7f9..4af3ba9 100644
--- a/chrome/chrome_tests_unit.gypi
+++ b/chrome/chrome_tests_unit.gypi
@@ -1311,6 +1311,7 @@
       'browser/extensions/api/log_private/syslog_parser_unittest.cc',
       'browser/extensions/updater/local_extension_cache_unittest.cc',
       'browser/metrics/chromeos_metrics_provider_unittest.cc',
+      'browser/metrics/perf/random_selector_unittest.cc',
       'browser/notifications/login_state_notification_blocker_chromeos_unittest.cc',
       'browser/ui/browser_finder_chromeos_unittest.cc',
       # TODO(zturner): Enable this on Windows. See