使用C++11 <random>实现高效的随机数生成

Question

我正试图理解C++11中的随机数生成功能应该如何使用。我的关注点是性能。

假设我们需要生成一系列介于0..k之间的随机整数，但k在每一步都会发生变化。最佳操作方式是什么？

例如：

for (int i=0; i < n; ++i) {
    int k = i; // of course this is more complicated in practice
    std::uniform_int_distribution<> dist(0, k);
    int random_number = dist(engine);
    // do something with random number
}

std::vector

to explicitly construct the distribution myself. While this is more verbose, it gives me complete control and insight into the underlying implementation.

std::uniform_real_distribution<> dist(0.0, 1.0);
for (int i=0; i < n; ++i) {
    int k = i; // of course this is more complicated in practice
    int random_number = std::floor( (k+1)*dist(engine) );
    // do something with random number
}

避免在每次迭代中构造新对象的方法。随机数经常用于重要性能的数字模拟中。在这些情况下，使用 <random> 的最佳方法是什么？

请不要回答“分析它”。分析是有效优化的一部分，但了解库的使用方式和该库的性能特征也同样重要。如果答案是依赖于标准库的实现，或者唯一知道的方法是分析它，那么我宁愿根本不使用<random>中的分布。相反，我可以使用自己的实现，这对我来说更加透明，并且在必要时更容易进行优化。

- Szabolcs

---

另一个需要考虑的因素是：像std::mt19937这样的生成器非常方便，它们是可移植的，并且其实现是标准规定的。在任何符合规范的实现中，使用给定种子的生成器必须产生相同的uint32_t随机序列。然而，分布适配器std::uniform_int_distribution没有这个保证，所以如果你使用它们，在改变编译器或其他因素的情况下，可能会得到不同的整数序列。这对于数值模拟可能是一个需要考虑的因素。 - Chris Beck

@ChrisBeck 我不知道这个，谢谢你指出来！ - Szabolcs

Answer 1

你可以做的一件事是拥有一个永久的分发对象，这样你每次只需要像这样创建param_type对象：

template<typename Integral>
Integral randint(Integral min, Integral max)
{
    using param_type =
        typename std::uniform_int_distribution<Integral>::param_type;

    // only create these once (per thread)
    thread_local static std::mt19937 eng {std::random_device{}()};
    thread_local static std::uniform_int_distribution<Integral> dist;

    // presumably a param_type is cheaper than a uniform_int_distribution
    return dist(eng, param_type{min, max});
}

- Galik

---

我并没有看到哪里写明了构造函数是编译时复杂度：D::param_type 并没有构造 param_type，而是产生了一个类型。 - Revolver_Ocelot

Answer 2

为了最大化性能，首先要考虑不同的伪随机数生成器(PRNG)，例如 xorshift128+。据报道，对于64位随机数，它的速度比mt19937快两倍以上；请参见http://xorshift.di.unimi.it/。而且，它可以用几行代码实现。

此外，如果您不需要"完美平衡"的均匀分布且您的k远小于2^64（很可能如此），我建议您仅编写以下内容：

uint64_t temp = engine_64(); // generates 0 <= temp < 2^64
int random_number = temp % (k + 1); // crop temp to 0,...,k

请注意，整数除法和模运算操作不是很快的。例如，在英特尔Haswell处理器上，对于64位数字，它们需要39-103个处理器周期，这可能比调用MT19937或xorshift+引擎要长得多。

- Daniel Langr

---

据报道，对于64位随机数，它的速度比mt19937快两倍以上。如果您不需要MT的周期，那么您可以使用xorshift128。如果您不需要xorshift的质量和周期，甚至可以使用LCG，它将是最快的。你知道，有些事情叫做权衡... - Severin Pappadeux