2

我正在创建一个陷阱，我想知道哪个随机数生成器最适合在插入时生成优先级。

数据集长约 6000 条。

我正在修改提供给我们的现有模板类（主要是声明的没有定义的方法）。预定义的生成器std::default_random_engine仅生成伪随机数。我想知道，这个生成器是否足够，如果没有，有什么替代方案？数据将一次性从文件中读取。

随机数生成器声明为：

std::default_random_engine* generator_;

仅在包装类的构造函数中创建时使用

TreapItem<K, T>(key, data, (*generator_)())

我希望尽可能少地发生碰撞。是否std::default_random_engine* generator_;足以实现没有碰撞，或者是否需要其他发电机？

编辑：我更喜欢均匀分布，或者接近它的东西。然而，正态分布也可能起作用。

指向生成器的指针在给定的代码中，乍一看它并没有作为缺陷出现。

4

1 回答 1

3

这是 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++ 默认值的性能令人惊讶，仅比简单的 RNG 慢 3-5 倍。最好的标准似乎是带有进位版本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
于 2019-05-02T22:46:46.017 回答