OLD | NEW |
---|---|
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "base/rand_util.h" | 5 #include "base/rand_util.h" |
6 | 6 |
7 #include <limits> | 7 #include <limits> |
8 | 8 |
9 #include "testing/gtest/include/gtest/gtest.h" | 9 #include "testing/gtest/include/gtest/gtest.h" |
10 | 10 |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
54 EXPECT_NE(0, accumulator); | 54 EXPECT_NE(0, accumulator); |
55 } | 55 } |
56 | 56 |
57 // Make sure that it is still appropriate to use RandGenerator in conjunction | 57 // Make sure that it is still appropriate to use RandGenerator in conjunction |
58 // with std::random_shuffle(). | 58 // with std::random_shuffle(). |
59 TEST(RandUtilTest, RandGeneratorForRandomShuffle) { | 59 TEST(RandUtilTest, RandGeneratorForRandomShuffle) { |
60 EXPECT_EQ(base::RandGenerator(1), 0U); | 60 EXPECT_EQ(base::RandGenerator(1), 0U); |
61 EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(), | 61 EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(), |
62 std::numeric_limits<int64>::max()); | 62 std::numeric_limits<int64>::max()); |
63 } | 63 } |
64 | |
65 TEST(RandUtilTest, RandGeneratorIsUniform) { | |
brettw
2011/05/27 18:13:21
I'm not super excited about this test. It seems by
Paweł Hajdan Jr.
2011/05/27 19:28:11
Right, everything based on randomness is quite har
Jói
2011/05/27 19:41:48
That wouldn't verify that the random distribution
| |
66 // Verify that RandGenerator has a uniform distribution. This is a | |
67 // regression test that consistently failed when RandGenerator was | |
68 // implemented this way: | |
69 // | |
70 // return base::RandUint64() % max; | |
71 // | |
72 // The worst case for such an implementation is e.g. a top of range | |
73 // that is 2/3rds of the way to MAX_UINT64, in which case the bottom | |
74 // half of the range would be twice as likely to occur as the top | |
75 // half, assuming a naive modulus implementation of RandGenerator. | |
76 const uint64 kTopOfRange = (std::numeric_limits<uint64>::max() / 3L) * 2L; | |
77 const uint64 kExpectedAverage = kTopOfRange / 2L; | |
78 const uint64 kAllowedVariance = kExpectedAverage / 100L; // 1% either way. | |
Paweł Hajdan Jr.
2011/05/27 19:28:11
nit: 1% seems quite strict, how about something mo
Jói
2011/05/27 19:41:48
The test already passes in an average of 14 ms wal
| |
79 const int kMaxAttempts = 1000000; | |
80 const int kReportEveryNAttempts = 10000; | |
81 | |
82 double cumulative_average = 0.0; | |
83 int count = 0; | |
84 while (count < kMaxAttempts) { | |
Paweł Hajdan Jr.
2011/05/27 19:28:11
nit: Why not a for loop then?
Jói
2011/05/27 19:41:48
Because I want to test the value of count after th
| |
85 uint64 value = base::RandGenerator(kTopOfRange); | |
86 cumulative_average = (count * cumulative_average + value) / (count + 1); | |
87 | |
88 // Don't quit too quickly for things to start converging. | |
89 if (count > 1000) { | |
Ilya Sherman
2011/05/27 19:23:26
nit: As long as you're making everything else a na
Jói
2011/05/27 19:41:48
Done.
| |
90 if (kExpectedAverage - kAllowedVariance < cumulative_average && | |
91 cumulative_average < kExpectedAverage + kAllowedVariance) { | |
92 break; | |
93 } | |
94 } | |
95 | |
96 if (count >= kReportEveryNAttempts && count % kReportEveryNAttempts == 0) { | |
brettw
2011/05/27 18:22:20
I don't think tests should be printing stuff out.
Ilya Sherman
2011/05/27 19:23:26
Yes, please remove these printf()'s, or find a way
Paweł Hajdan Jr.
2011/05/27 19:28:11
Yeah, and also it's better to use LOG or gtest mac
Jói
2011/05/27 19:41:48
Done.
Jói
2011/05/27 19:41:48
Done.
Jói
2011/05/27 19:41:48
Done.
| |
97 if (count == kReportEveryNAttempts) | |
98 printf("Expected average is %ld\n", kExpectedAverage); | |
99 printf("Cumulative average hasn't converged, is %.0f after %d samples.\n", | |
100 cumulative_average, count); | |
101 } | |
102 | |
103 ++count; | |
104 } | |
105 | |
106 ASSERT_LT(count, kMaxAttempts); | |
107 } | |
OLD | NEW |