random_number_generator_unittest.cc 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
  1. // Copyright 2018 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "base/bind.h"
  5. #include "base/callback.h"
  6. #include "media/learning/impl/test_random_number_generator.h"
  7. #include "testing/gtest/include/gtest/gtest.h"
  8. namespace media {
  9. class RandomNumberGeneratorTest : public testing::Test {
  10. public:
  11. RandomNumberGeneratorTest() : rng_(0) {}
  12. void GenerateAndVerify(base::RepeatingCallback<int64_t()> generate,
  13. int64_t lower_inclusive,
  14. int64_t upper_inclusive) {
  15. const size_t n = 10000;
  16. std::map<int64_t, size_t> counts;
  17. for (size_t i = 0; i < n; i++)
  18. counts[generate.Run()]++;
  19. // Verify that it's uniform over |lower_inclusive| and
  20. // |upper_inclusive|, at least approximately.
  21. size_t min_counts = counts[lower_inclusive];
  22. size_t max_counts = min_counts;
  23. size_t total_counts = min_counts;
  24. for (int64_t i = lower_inclusive + 1; i <= upper_inclusive; i++) {
  25. size_t c = counts[i];
  26. if (c < min_counts)
  27. min_counts = c;
  28. if (c > max_counts)
  29. max_counts = c;
  30. total_counts += c;
  31. }
  32. // See if the min and the max are too far from the expected counts.
  33. // Note that this will catch only egregious problems. Also note that
  34. // random variation might actually exceed these limits fairly often.
  35. // It's only because the test rng has no variation that we know it
  36. // won't happen. However, there might be reasonable implementation
  37. // changes that trip these tests (deterministically!); manual
  38. // verification of the result is needed in those cases.
  39. //
  40. // These just catch things like "rng range is off by one", etc.
  41. size_t expected_counts = n / (upper_inclusive - lower_inclusive + 1);
  42. EXPECT_LT(max_counts, expected_counts * 1.05);
  43. EXPECT_GT(max_counts, expected_counts * 0.95);
  44. EXPECT_LT(min_counts, expected_counts * 1.05);
  45. EXPECT_GT(min_counts, expected_counts * 0.95);
  46. // Verify that the counts between the limits accounts for all of them.
  47. // Otherwise, some rng values were out of range.
  48. EXPECT_EQ(total_counts, n);
  49. }
  50. // We use TestRandomNumberGenerator, since we really want to test the base
  51. // class method implementations with a predictable random source.
  52. TestRandomNumberGenerator rng_;
  53. };
  54. TEST_F(RandomNumberGeneratorTest, ExclusiveUpTo) {
  55. // Try Generate with something that's not a divisor of max_int, to try to
  56. // catch any bias. I.e., an implementation like "rng % range" should fail
  57. // this test.
  58. //
  59. // Unfortunately, it won't.
  60. //
  61. // With uint64_t random values, it's unlikely that we would ever notice such a
  62. // problem. For example, a range of size three would just remove ~three from
  63. // the upper range of the rng, and it's unlikely that we'd ever pick the three
  64. // highest values anyway. If, instead, we make |range| really big, then we're
  65. // not going to sample enough points to notice the deviation from uniform.
  66. //
  67. // However, we still look for issues like "off by one".
  68. const uint64_t range = 5;
  69. GenerateAndVerify(base::BindRepeating(
  70. [](RandomNumberGenerator* rng, uint64_t range) {
  71. return static_cast<int64_t>(rng->Generate(range));
  72. },
  73. &rng_, range),
  74. 0, range - 1);
  75. }
  76. TEST_F(RandomNumberGeneratorTest, DoublesStayInRange) {
  77. const double limit = 1000.5;
  78. int num_non_integer = 0;
  79. for (int i = 0; i < 1000; i++) {
  80. double v = rng_.GenerateDouble(limit);
  81. EXPECT_GE(v, 0.);
  82. EXPECT_LT(v, limit);
  83. // Also count how many non-integers we get.
  84. num_non_integer += (v != static_cast<int>(v));
  85. }
  86. // Expect a lot of non-integers.
  87. EXPECT_GE(num_non_integer, 900);
  88. }
  89. } // namespace media