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

chrome/browser/metrics/perf/random_selector_unittest.cc

+// 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%).

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

Does this mean the test is expected to be flaky some percent of the time?

[dhsharp, 2015/09/15 18:21:32]

No, not since we added the non-random "CustomRNG". But there will still be some
fuzz.

+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);
+}