c++ - 通用随机数生成

Question

C++11 为 C 的 rand() 引入了一个非常优越的随机数库.在 C 中，您经常会看到以下代码:

srand(time(0));
rand() % MAX + MIN;

因为 time(0)以秒为单位返回当前时间，对程序的快速连续调用将产生相同的数字序列。对此的快速解决方法是以纳秒为单位提供种子:

 struct timeval time; 
 gettimeofday(&time,NULL);
 srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

当然，这并不能改变 rand() 的事实。被普遍认为是糟糕的，优秀的替代方案要么是不可移植的(如 Linux 的 random() )，要么依赖于第三方库(如 Boost)。

在 C++11 中，我知道生成好的随机数的最短程序是:

#include <iostream>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<int> dist(1, 10);
    std::cout << dist(mt);
}

std::random_device不可携带且 std::default_random_engine不鼓励，因为它可能会选择较差的引擎，例如 std::rand .事实上， std::random_shuffle已弃用和 std::shuffle出于这个原因是首选。通常，我看到人们说使用 chrono 来提供种子:

std::chrono::high_resolution_clock::now().time_since_epoch().count()

这不仅很难记住，而且当我们想要使用纳秒时看起来更难看:

using namespace std::chrono;
std::mt19937 mt(duration_cast<nanoseconds>(high_resolution_clock::now()
                                      .time_since_epoch()).count());

C 方法看起来很可取，因为它不需要那么多
样板。

random_device最简单，因为它不需要丑陋的
单线，即使它是非可移植的。

mt19937比default_random_engine更难记住.

哪种方法最好？

Answer 1

(1) 了解可用的生成器并选择最适合工作的生成器

(2) 煮种子熵，绘制标准度量(如 256 位)，将其打印到日志

(3) 将您的标准种子块转换为适合生成器的大小的 seed_seq
有问题并播种 genny

关于(1):标准库中的生成器使用起来有点棘手，因为它们都有一些特殊性，并且它们都系统地失败了像 TestU01 这样的标准 PRNG 测试。您必须了解它们的特定缺陷才能判断它们的适用性。如果做不到这一点，请使用 mt19937 或 ranlux，将它们播种好并希望最好。使用 typedef - 你自己的 - 允许你切换和试验不同的 Sprite 。 typeid(rng_t).name() 识破伪装并记录真实姓名。

关于(2):你不能将原始的、块状的熵传递给播种程序；如果你这样做，那么小的种子差异只会导致小的状态差异。熵必须被煮成光滑的糊状物，其中每一位都以 50% 的概率依赖于原始输入的每一位。这包括像 1, 2, 3, ... 这样的输入，取固定标准量的位汤使整个事情变得易于管理，例如打印到屏幕或日志以确保必要时的可重复性。不用说，如果您使用 1、2、42 等种子编号，而不是随机种子，那么您可以将它们打印到日志中，而不是将其打印到位汤提取物中。使用您自己的钻头意味着您不受半途而废的播种功能的支配，甚至像 1、2、3 等“不足”的种子也会为您提供截然不同的生成器状态(序列)。

关于 (3):一些生成器 - 比如 mt19937 - 具有巨大的内部状态，因此您需要大量扩展 256 位(或其他)标准种子。不幸的是，标准库不包含任何非常适合此任务的生成器，也没有用于将生成器转换为 seed_seq 的适配器。

我会使用 xorshift* 、KISS、run(数值食谱)或 4x32 Tausworthe(又名 lfsr113)，但这些都不在库中。该库也没有任何合适的混合功能(钻头研磨机)。

我在 a similar topic 中发布了 murmur 混合器的代码 - 一个简单且极其有效的位混合函数；我在这里给出经典的 KISS 和 Tausworthe，因为我在网上找不到合适的、干净的引用。

struct KISS {  uint32_t a, b, c, d; ... };

uint32_t KISS::cycle ()
{
   a = (a & 0xFFFF) * 36969 + (a >> 16);         // 16-bit MWC, a.k.a. znew()
   b = (b & 0xFFFF) * 18000 + (b >> 16);         // 16-bit MWC, a.k.a. wnew()
   c = c * 69069 + 1234567;                      // 32-bit LCG, a.k.a. CONG()(
   d ^= d << 13;  d ^= d >> 17;  d ^= d << 5;    // 32-bit XorShift a.k.a. SHR3(), corrected

   return (((a << 16) | (b & 0xFFFF)) ^ c) + d;  // mixing function (combiner)
}

合并的陶斯沃思:

struct LFSR113 {  uint32_t a, b, c, d; ... };

uint32_t LFSR113::cycle ()
{
   a = ((a ^ (a <<  6)) >> 13) ^ ((a & ~0x01) << 18);  // 31 bits
   b = ((b ^ (b <<  2)) >> 27) ^ ((b & ~0x07) <<  2);  // 29 bits
   c = ((c ^ (c << 13)) >> 21) ^ ((c & ~0x0F) <<  7);  // 28 bits
   d = ((d ^ (d <<  3)) >> 12) ^ ((d & ~0x7F) << 13);  // 25 bits

   return a ^ b ^ c ^ d;
}

要用作主生成器，您必须调整禁止的种子(粘性状态)，但对于种子拉伸(stretch)(制作 seed_seq)，可以安全地忽略这一点。有很多替代方案，比如使用 std::vector 和一个简单的生成器 (LCG) 来制作一个不错的 seed_seq，但我更喜欢尝试过、值得信赖且经过彻底分析的解决方案，以最少的代码获得最大的 yield 。

这里显示的两个 4x32 生成器可以使用中国剩余定理进行步进，相反，任何状态都可以映射到整个序列中的唯一点(暂时忽略轨道之类的东西)。这使得它们和其他类似的生成器在不需要像 xorshift1024*(或 mt19937)这样的大枪时作为主要生成器很有吸引力。

在任何情况下，您都需要相当多的代码 - 例如头文件中的模板 - 为了使标准的 <random> 生成器简单、舒适和安全地使用。但它的努力是 100% 值得的。发电机不太热，但可以维修；其余的基础设施相当不错，它可以在很大程度上解决您的问题。

P.S.:一些实现(VC++)允许它将任何生成器传递给 seed() 函数，这让事情变得非常简单。其他 - gcc - 不要，这意味着如果您希望代码可移植，则必须执行 seed_seq 操作。如果你想让事情变得 super 简单，只需通过 murmur_mix() 传递你选择的种子，然后再将它们交给 seed() 并继续。

The wages of fear: 一旦你把你的魔法塞进了一个标题，实际的应用就很容易了。

#include "zrbj/rng_wrapper.hpp"
#include <random>
#include <typeinfo>

int main ()
{
   zrbj::seeded<std::mt19937> rng(42);

   std::cout << typeid(rng.wrapped_rng).name() << " -> " << rng();
}       

这会将生成器、42 和实际种子打印到日志中，除了将碎片粉碎并将它们塞入 mt19937 之外。编码一次，向后靠，享受。