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

chrome/browser/metrics/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 <cmath>
+#include <map>
+#include <string>
+
+#include <base/strings/string_util.h>

[Alexei Svitkine (slow), 2015/09/11 21:00:55]

""'s not <>'s.

[dhsharp, 2015/09/11 22:53:25]

Done.

+#include <gtest/gtest.h>

[dhsharp, 2015/09/11 22:53:25]

For gtest/gtest.h, I looked around and saw a ~50/50 split between <> and "". Not
sure which it should be...

+
+#include "chrome/browser/metrics/random_selector.h"

[Alexei Svitkine (slow), 2015/09/11 21:00:54]

Should be first include.

[dhsharp, 2015/09/11 22:53:25]

Done.

+
+using metrics::RandomSelector;

[Alexei Svitkine (slow), 2015/09/11 21:00:55]

Put this code in the metrics namespace instead.

[dhsharp, 2015/09/11 22:53:25]

Done.

+
+namespace {
+
+// 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_;
+};

[Alexei Svitkine (slow), 2015/09/11 21:00:55]

DISALLOW_COPY_AND_ASSIGN()

[dhsharp, 2015/09/11 22:53:25]

Done.

+
+// 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::vector<std::string>& next_value = random_selector->GetNext();
+    std::string joined = base::JoinString(next_value, " ");
+    (*results)[joined]++;
+  }
+}
+
+// This function tests whether the results are close enough to the odds (within
+// 1%).
+void CheckResultsAgainstOdds(
+    const std::vector<RandomSelector::OddsAndValue>& odds,
+    const std::map<std::string, int>& results) {
+  EXPECT_EQ(odds.size(), results.size());
+
+  const double odds_sum = RandomSelector::SumOdds(odds);
+  int results_sum = 0;
+  for (const auto& item : results) {
+    results_sum += item.second;
+  }
+
+  for (const auto& odd : odds) {
+    const auto result = results.find(base::JoinString(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);
+  }
+}
+
+const char* kCmdA[] = {"a", "1"};
+const char* kCmdB[] = {"b", "--help"};
+const char* kCmdC[] = {"c", "bar"};
+
+}  // namespace
+
+TEST(RandomSelector, SimpleAccessors) {
+  using OddsAndValue = RandomSelector::OddsAndValue;
+  std::vector<OddsAndValue> odds;
+  odds.push_back(OddsAndValue(1, kCmdA));
+  odds.push_back(OddsAndValue(3, kCmdB));
+  odds.push_back(OddsAndValue(107, kCmdC));
+  EXPECT_EQ(111.0L, RandomSelector::SumOdds(odds));
+  RandomSelector random_selector;
+  random_selector.SetOdds(odds);
+  EXPECT_EQ(3UL, random_selector.GetNumValues());
+}
+
+// Ensure RandomSelector is able to generate results from given odds.
+TEST(RandomSelector, GenerateTest) {
+  using OddsAndValue = RandomSelector::OddsAndValue;
+  const int kLargeNumber = 2000;
+  std::vector<RandomSelector::OddsAndValue> odds;
+  odds.push_back(OddsAndValue(1, kCmdA));
+  odds.push_back(OddsAndValue(2, kCmdB));
+  odds.push_back(OddsAndValue(3, kCmdC));
+  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);
+}
+