在 C++ 中为 treap 生成随机优先级
Generating random priorities for a treap in C++
我正在创建一个 treap,我想知道哪种随机数生成器最适合在插入时生成优先级。
数据集大约有 6000 条。
我正在修改提供给我们的现有模板 class(主要是没有定义的声明方法)。预定义的生成器是 std::default_random_engine
,它只生成伪随机数。我想知道,这个生成器是否足够,如果不够,有哪些替代方案?将一次性从一个文件中读取数据。
随机数生成器声明为:
std::default_random_engine* generator_;
仅在包装器的构造函数中创建时使用 class
TreapItem<K, T>(key, data, (*generator_)())
我希望碰撞次数尽可能少。 std::default_random_engine* generator_;
是否足以实现无碰撞,或者是否需要其他生成器?
编辑:我更喜欢均匀分布,或者接近它的东西。然而,正态分布也可能有效。
指向生成器的指针在给定的代码中,乍一看并没有出现缺陷。
这是 c++ 随机生成器的一个简单(但并不详尽!)基准测试
加上古老的 C rand 函数和一个简单的 rot-xor 生成器。
有一个简单的冒烟测试,从数字中间取几位,
但绝不是加密证明。
我认为它们都适用于随机二叉搜索树。
#include <random>
#include <iostream>
#include <chrono>
#include <stdlib.h>
struct rot_xor {
int32_t seed = 0x95abcfad;
inline uint32_t operator() () {
return seed = (seed << 1) ^ ((seed >> 31) & 0xa53a9be9);
}
};
struct crand {
int32_t seed = 0x95abcfad;
inline uint32_t operator() () {
return rand();
}
};
template <class Generator>
void benchmark(std::vector<int> &histo) {
Generator r;
int mask = histo.size() - 1;
for (int i = 0; i != 10000000; ++i) {
uint32_t val = (uint32_t)r();
histo[(val>>16) & mask]++;
}
}
int main() {
using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::microseconds;
for (int i = 0; i != 9; ++i) {
std::vector<int> histo(0x100);
auto t0 = high_resolution_clock::now();
switch (i) {
case 0: benchmark<std::minstd_rand0>(histo); break;
case 1: benchmark<std::minstd_rand>(histo); break;
case 2: benchmark<std::mt19937>(histo); break;
case 3: benchmark<std::mt19937_64>(histo); break;
case 4: benchmark<std::ranlux24_base>(histo); break;
case 5: benchmark<std::ranlux48_base>(histo); break;
case 6: benchmark<std::default_random_engine>(histo); break;
case 7: benchmark<crand>(histo); break;
case 8: benchmark<rot_xor>(histo); break;
}
auto t1 = high_resolution_clock::now();
int min_histo = histo[0];
int max_histo = histo[0];
for (auto h : histo) {
min_histo = std::min(min_histo, h);
max_histo = std::max(max_histo, h);
}
std::cout << "test " << i << " took " << duration_cast<microseconds>(t1-t0).count() << "us\n";
std::cout << " smoke test = " << min_histo << " .. " << max_histo << "\n";
}
}
对于相当复杂的 C++ 默认值,结果显示出惊人的性能,只有 3-5
比简单的 RNG 慢 1 倍。最好的标准似乎是带有进位版本 ranlux_* 的减法。我认为包含除法的旧 C rand() 函数毫无疑问是最慢的。
test 0 took 58066us
smoke test = 38486 .. 39685
test 1 took 39310us
smoke test = 38533 .. 39604
test 2 took 26382us
smoke test = 38503 .. 39591
test 3 took 29146us
smoke test = 38591 .. 39670
test 4 took 27721us <- not bad, ranlux24
smoke test = 38419 .. 39597
test 5 took 27310us
smoke test = 38608 .. 39622
test 6 took 38629us
smoke test = 38486 .. 39685
test 7 took 65377us
smoke test = 38551 .. 39541
test 8 took 10984us <-- fastest (rot-xor)
smoke test = 38656 .. 39710
我正在创建一个 treap,我想知道哪种随机数生成器最适合在插入时生成优先级。
数据集大约有 6000 条。
我正在修改提供给我们的现有模板 class(主要是没有定义的声明方法)。预定义的生成器是 std::default_random_engine
,它只生成伪随机数。我想知道,这个生成器是否足够,如果不够,有哪些替代方案?将一次性从一个文件中读取数据。
随机数生成器声明为:
std::default_random_engine* generator_;
仅在包装器的构造函数中创建时使用 class
TreapItem<K, T>(key, data, (*generator_)())
我希望碰撞次数尽可能少。 std::default_random_engine* generator_;
是否足以实现无碰撞,或者是否需要其他生成器?
编辑:我更喜欢均匀分布,或者接近它的东西。然而,正态分布也可能有效。
指向生成器的指针在给定的代码中,乍一看并没有出现缺陷。
这是 c++ 随机生成器的一个简单(但并不详尽!)基准测试 加上古老的 C rand 函数和一个简单的 rot-xor 生成器。
有一个简单的冒烟测试,从数字中间取几位, 但绝不是加密证明。
我认为它们都适用于随机二叉搜索树。
#include <random>
#include <iostream>
#include <chrono>
#include <stdlib.h>
struct rot_xor {
int32_t seed = 0x95abcfad;
inline uint32_t operator() () {
return seed = (seed << 1) ^ ((seed >> 31) & 0xa53a9be9);
}
};
struct crand {
int32_t seed = 0x95abcfad;
inline uint32_t operator() () {
return rand();
}
};
template <class Generator>
void benchmark(std::vector<int> &histo) {
Generator r;
int mask = histo.size() - 1;
for (int i = 0; i != 10000000; ++i) {
uint32_t val = (uint32_t)r();
histo[(val>>16) & mask]++;
}
}
int main() {
using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::microseconds;
for (int i = 0; i != 9; ++i) {
std::vector<int> histo(0x100);
auto t0 = high_resolution_clock::now();
switch (i) {
case 0: benchmark<std::minstd_rand0>(histo); break;
case 1: benchmark<std::minstd_rand>(histo); break;
case 2: benchmark<std::mt19937>(histo); break;
case 3: benchmark<std::mt19937_64>(histo); break;
case 4: benchmark<std::ranlux24_base>(histo); break;
case 5: benchmark<std::ranlux48_base>(histo); break;
case 6: benchmark<std::default_random_engine>(histo); break;
case 7: benchmark<crand>(histo); break;
case 8: benchmark<rot_xor>(histo); break;
}
auto t1 = high_resolution_clock::now();
int min_histo = histo[0];
int max_histo = histo[0];
for (auto h : histo) {
min_histo = std::min(min_histo, h);
max_histo = std::max(max_histo, h);
}
std::cout << "test " << i << " took " << duration_cast<microseconds>(t1-t0).count() << "us\n";
std::cout << " smoke test = " << min_histo << " .. " << max_histo << "\n";
}
}
对于相当复杂的 C++ 默认值,结果显示出惊人的性能,只有 3-5 比简单的 RNG 慢 1 倍。最好的标准似乎是带有进位版本 ranlux_* 的减法。我认为包含除法的旧 C rand() 函数毫无疑问是最慢的。
test 0 took 58066us
smoke test = 38486 .. 39685
test 1 took 39310us
smoke test = 38533 .. 39604
test 2 took 26382us
smoke test = 38503 .. 39591
test 3 took 29146us
smoke test = 38591 .. 39670
test 4 took 27721us <- not bad, ranlux24
smoke test = 38419 .. 39597
test 5 took 27310us
smoke test = 38608 .. 39622
test 6 took 38629us
smoke test = 38486 .. 39685
test 7 took 65377us
smoke test = 38551 .. 39541
test 8 took 10984us <-- fastest (rot-xor)
smoke test = 38656 .. 39710