优化使用C++11随机数生成器

Question

我正在编写一份物理模拟代码，其中大量使用了随机数。我刚刚第一次对我的代码进行了剖析，所以我可能在读取输出时出现错误，但我发现这一行首先出现：

   %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name  
 90.09     21.88    21.88   265536     0.08     0.08  std::mersenne_twister_engine<unsigned long, 32ul, 624ul, 397ul, 31ul, 2567483615ul, 11ul, 4294967295ul, 7ul, 2636928640ul, 15ul, 4022730752ul, 18ul, 1812433253ul>::operator()()

似乎意味着生成数值的生成器占据了90% 的时间。我之前写过一篇帖子询问在每个循环中不构建随机概率分布是否可以节省时间，但经过尝试和计时后并没有帮助 (Is defining a probability distribution costly? ) 。有没有优化随机数生成的常见选项？提前感谢您的回答，我的模拟（目前的状态）持续几天，因此减少90% 的计算时间将是一项重大进展。

- Liam

---

这取决于你关心什么，不同情况下有大量不同的伪随机数生成器可供选择，你想要线性的还是非线性的？在无符号整数、浮点数、整数上运行的东西...？ - user2485710

你是否考虑在运行模拟之前生成随机数，或者这不可能吗？ - AndersK

@MSalters 您说的线程是指什么？并行处理吗？ - Liam

@user2485710：我需要适用于无符号整数和浮点数的东西。你所说的线性是什么意思？到目前为止，我的要求是拥有一个非常大的周期和...快速 =) - Liam

@user2485710 感谢您的指定，实际上我已经对随机数生成器感到不满意了（在我的输出数据中显示一些奇怪的相关性），我将来可能会避免使用它 ;) - Liam

Answer 1

在任何随机数生成器（RNG）中，效率（即速度和状态字节数）与“随机性”之间总是存在折衷。梅森旋转演算法具有相当好的随机性（如果您使用高熵种子，例如std::random_device提供的种子），但速度较慢且状态较大。 std::minstd_rand或std::knuth_b（线性同余式）更快，ranlux48（斐波那契数列）更快，但随机性较差（未能通过更少的随机性测试，即具有一些非随机的频谱特性）。只需进行实验和测试即可确定是否满意所提供的随机性（即随机数据中没有意外的相关性）。

---

编辑：1 当然，所有这些RNG都不是真正的随机数，并且对于加密来说也不够随机。如果需要加密，请使用std：：random_device，但不要抱怨速度。 2 在并行计算中（应该考虑），请使用thread_local RNG，每个RNG都用另一个种子初始化。

- Walter

---

谢谢您的建议，我使用的第一个随机生成器（提供的crand）在我的数据中显示了一些奇怪的相关性。在阅读他们的文档后，我可能会尝试您的建议！ - Liam

@Liam 在另一端的是CSPRNGs，我可以几乎保证会更慢，但你可以放心，知道你所提到的相关性不会成为问题（除了Dual_EC_DRBG; 感谢NSA）。Hash-DRBG或HMAC-DRBG与强大的加密摘要算法（例如SHA256）结合使用，肯定会给你想要的散列，但如果你认为MT很昂贵，那么你还没见过什么。然而，对于非LCG算法，你可能会发现MT的2^19937-1周期与你可能得到的一样好。 - WhozCraig

Answer 2

如果你的代码大部分时间都在生成随机数，那么你可能需要花些时间选择最适合你应用程序的最佳算法，并自己实现它。Mersenne Twister是一种相当快速的算法，而且具有很好的随机性，但你总可以为了更快的速度而牺牲一些所生成的随机数的质量。这将取决于你的模拟需要什么以及你正在生成的数字类型（整数或浮点数）。如果你绝对需要良好的随机性，那么Mersenne Twister可能已经是你最好的选择之一。否则，你可能需要在代码中实现一个简单的线性同余发生器。

另一件需要注意的事情是，如果你的代码是并行的，你应该使用可重入版本的随机数生成器，并确保不同的线程使用自己的内部状态变量来生成随机数。否则，为了避免覆盖生成器的内部状态变量，互斥锁会严重降低你的代码速度。请注意，许多库生成器都不是可重入的。如果你的代码不是并行的，你应该考虑将其并行化，并使用一个单独的线程来填充一个随机数列表，以供你的模拟消耗。另一个选择是使用GPU并行生成随机数。

以下是比较不同生成器性能的链接:

http://www.boost.org/doc/libs/1_38_0/libs/random/random-performance.html https://www.gnu.org/software/gsl/manual/html_node/Random-Number-Generator-Performance.html

- Guilherme Amadio

---

“使用可重入版本的RNG” - 因为我们正在讨论C++11，所以这不是一个大问题。 RNG现在是适当的对象，通常的对象规则适用：它们不是可重入的，如果线程需要共享一个对象，则需要互斥锁。 - MSalters

“implement it yourself”这个回答是最糟糕的答案之一。 - Walter

当库代码占用90%的运行时间时，自己实现某些功能是完全有效的策略。随机数生成器并不那么复杂。使用自己的代码，您可以找到和修复瓶颈，而这在库代码中是做不到的。我曾经通过摆脱标准库并实现自己的堆、映射和列表结构来使仿真代码的速度翻倍。此外，有一些现成的快速实现可供他下载并集成到自己的代码中。 - Guilherme Amadio

Answer 3

使用专用的随机数库。

我建议使用WELL512（链接包含论文和源代码）。

- Wilbert

---

那有什么用呢？代码将不太可移植，而且也不清楚它是否会更快。你仍然面临着效率和随机性之间的基本问题。 - Walter

当然可以。另一方面，Well512被认为比mersenne twister更高效，同时提供类似的保证。目前得票最高的答案说“自己实现” - 我认为使用专门用于手头任务的库是更好的解决方案。 - Wilbert

Wilbert，同意你的 implement it yourself。 - Walter

Answer 4

Marsaglia的KISS RNG速度快，非常适合模拟工作。我假设您不需要加密质量。

- rossum

---

严谨的注释：您提供的版本假设无符号长整型恰好有32位。 - loreb

有许多不同尺寸的KISS版本。那只是我找到的第一个版本。 - rossum

我知道（我喜欢那个随机数生成器！）-- 我的观点是这个特定版本是为32位设计的，但无符号长整型可能更大。 - loreb

Answer 5

如果随机性要求允许，您可以使用 RDTSC指令 来获取随机数，例如 int from0to9 = rdtsc() % 10。

- ArtemGr