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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include <iostream>
#include <string>
#include <array>
#include <cstdint>
#include <limits>
#include <random>
#include <utility>
#define PHMAP_ALLOCATOR_NOTHROW 1
#include <parallel_hashmap/phmap.h>
// this is probably the fastest high quality 64bit random number generator that exists.
// Implements Small Fast Counting v4 RNG from PractRand.
class sfc64 {
public:
using result_type = uint64_t;
// no copy ctors so we don't accidentally get the same random again
sfc64(sfc64 const&) = delete;
sfc64& operator=(sfc64 const&) = delete;
sfc64(sfc64&&) = default;
sfc64& operator=(sfc64&&) = default;
sfc64(std::array<uint64_t, 4> const& _state)
: m_a(_state[0])
, m_b(_state[1])
, m_c(_state[2])
, m_counter(_state[3]) {}
static constexpr uint64_t(min)() {
return (std::numeric_limits<uint64_t>::min)();
}
static constexpr uint64_t(max)() {
return (std::numeric_limits<uint64_t>::max)();
}
sfc64()
: sfc64(UINT64_C(0x853c49e6748fea9b)) {}
sfc64(uint64_t _seed)
: m_a(_seed)
, m_b(_seed)
, m_c(_seed)
, m_counter(1) {
for (int i = 0; i < 12; ++i) {
operator()();
}
}
void seed() {
*this = sfc64{std::random_device{}()};
}
uint64_t operator()() noexcept {
auto const tmp = m_a + m_b + m_counter++;
m_a = m_b ^ (m_b >> right_shift);
m_b = m_c + (m_c << left_shift);
m_c = rotl(m_c, rotation) + tmp;
return tmp;
}
std::array<uint64_t, 4> state() const {
return {{m_a, m_b, m_c, m_counter}};
}
void state(std::array<uint64_t, 4> const& s) {
m_a = s[0];
m_b = s[1];
m_c = s[2];
m_counter = s[3];
}
private:
template <typename T>
T rotl(T const x, int k) {
return (x << k) | (x >> (8 * sizeof(T) - k));
}
static constexpr int rotation = 24;
static constexpr int right_shift = 11;
static constexpr int left_shift = 3;
uint64_t m_a;
uint64_t m_b;
uint64_t m_c;
uint64_t m_counter;
};
static inline std::string to_str(uint64_t x) {
std::string res(4, '1');
x = (x >> 48) ^ (x >> 32) ^ (x >> 16) ^ x; // combine 64 bits > 16 lsb
for (size_t i=0; i<4; ++i) {
res[i] = 'a' + (x & 0xF);
x >>= 4;
}
return res;
}
int main()
{
using Map = phmap::flat_hash_map<std::string, uint32_t>;
Map map;
map.reserve((size_t)(65536 * 1.1)); // we will create a maximun of 65536 different strings
sfc64 rng(123);
constexpr size_t const n = 50000000;
for (size_t i = 0; i < n; ++i) {
auto s = to_str(rng());
map[s]++;
map[s]++;
map[s]++;
map[s]++;
map[s]++;
map[s]++;
map[s]++;
map[s]++;
map[s]++;
map[s]++;
}
uint64_t cnt = 0;
for (const auto& s : map) {
if (++cnt == 6) break;
std::cout << s.first << ": " << s.second << '\n';
}
return 0;
}
|
