1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include "hash_primes.h"
#include <library/cpp/testing/unittest/registar.h>
#include <util/generic/vector.h>
#include <util/string/builder.h>
#include <util/random/fast.h>
Y_UNIT_TEST_SUITE(TestHashPrimes) {
Y_UNIT_TEST(Test1) {
UNIT_ASSERT_VALUES_EQUAL(HashBucketCount(1), 7);
UNIT_ASSERT_VALUES_EQUAL(HashBucketCount(6), 7);
UNIT_ASSERT_VALUES_EQUAL(HashBucketCount(7), 7);
UNIT_ASSERT_VALUES_EQUAL(HashBucketCount(8), 17);
}
static TVector<size_t> Numbers() {
TVector<size_t> numbers;
TFastRng64 rng{961923};
size_t k = 1;
for (size_t j = 0; j < 8000; ++j) {
numbers.push_back(rng.GenRand());
numbers.push_back(k *= 57);
}
for (size_t p = 1; p != 0; p <<= 1) {
for (size_t offset : {-2, -1, 0, 1, 2}) {
numbers.push_back(p + offset);
}
}
return numbers;
}
static TVector<size_t> Divisors() {
TVector<size_t> divisors;
divisors.push_back(HashBucketCountExt(0)());
for (;;) {
const size_t prevSize = divisors.back();
const size_t nextSize = HashBucketCountExt(prevSize + 1)();
if (nextSize <= prevSize) {
break;
}
divisors.push_back(nextSize);
}
return divisors;
}
Y_UNIT_TEST(Remainder) {
const TVector<size_t> numbers = Numbers();
const TVector<size_t> divisors = Divisors();
auto testDivisor = [&](const auto& c) {
for (size_t n : numbers) {
UNIT_ASSERT_VALUES_EQUAL_C(n % c(), c.Remainder(n), (TStringBuilder() << "n=" << n << "; d=" << c()));
}
};
for (size_t d : divisors) {
const auto c = HashBucketCountExt(d);
UNIT_ASSERT_VALUES_EQUAL_C(d, c(), (TStringBuilder() << "d=" << d));
testDivisor(c);
}
testDivisor(::NPrivate::THashDivisor::One());
}
Y_UNIT_TEST(MisleadingHints) {
TFastRng64 rng{332142};
TVector<size_t> cases = Numbers();
for (size_t d : Divisors()) {
cases.push_back(d);
}
for (size_t c : cases) {
for (size_t reps = 0; reps < 3; ++reps) {
const i8 hint = rng.Uniform(256) - 128;
UNIT_ASSERT_VALUES_EQUAL_C(HashBucketCountExt(c)(), HashBucketCountExt(c, hint)(), (TStringBuilder() << "c=" << c << "; hint=" << hint));
}
}
}
}
|
