确定性地分叉随机数生成器？
Forking a random number generator deterministically?
我正在使用 std::mt19937 生成确定性随机数。我想将它传递给函数，这样我就可以控制它们的随机源。我可以做 int foo(std::mt19937& rng);，但我想并行调用 foo 和 bar，所以这行不通。即使我将生成函数放在互斥锁后面（因此每次调用 operator() 都会执行 std::lock_guard lock(mutex); return rng();），并行调用 foo 和 bar 也不会是确定性的，因为互斥量竞争。
我觉得在概念上我应该能够做到这一点：
auto fooRNG = std::mt19937(rng()); // Seed a RNG with the output of `rng`.
auto barRNG = std::mt19937(rng());
parallel_invoke([&] { fooResult = foo(fooRNG); },
[&] { barResult = bar(barRNG); });
我在这里“分叉”rng 到两个具有不同种子的新的。由于 fooRNG 和 barRNG 是确定性播种的，因此它们应该是随机且独立的。
- 这个通用要点可行吗？
- 这个特定的实现是否足够（我怀疑）？
扩展问题：假设我想在一系列索引值上并行调用 baz(int n, std::mt19937&)，比如
auto seed = rng();
parallel_for(range(0, 1 << 20),
[&](int i) {
auto thisRNG = std::mt19937(seed ^ i); // Deterministically set up RNGs in parallel?
baz(i, thisRNG);
});
类似的东西应该有用，对吧？也就是说，只要我们给它足够的状态位？
更新：
查看 std::seed_seq，它看起来（？）像是旨在将不那么随机的种子变成高质量的种子：How to properly initialize a C++11 std::seed_seq
也许我想要的是
std::mt19937 fork(std::mt19937& rng) {
return std::mt19937(std::seed_seq({rng()}));
}
或更一般地说：
//! Represents a state that can be used to generate multiple
//! distinct deterministic child std::mt19937 instances.
class rng_fork {
std::mt19937::result_type m_seed;
public:
rng_fork(std::mt19937& rng) : m_seed(rng()) {}
// Copy is explicit b/c I think it's a correctness footgun:
explicit rng_fork(const rng_fork&) = default;
//! Make the ith fork: a deterministic but well-seeded
//! RNG based off the internal seed and the given index:
std::mt19937 ith_fork(std::mt19937::result_type index) const {
return std::mt19937(std::seed_seq({m_seed, index}));
}
};
那么初始示例将变为
auto fooRNG = fork(rng);
auto barRNG = fork(rng);
parallel_invoke([&] { fooResult = foo(fooRNG); },
[&] { barResult = bar(barRNG); });
和
auto fork_point = rng_fork{rng};
parallel_for(range(0, 1 << 20),
[&](int i) {
auto thisRNG = fork_point.ith_fork(i); // Deterministically set up a RNG in parallel.
baz(i, thisRNG);
});
std::seed_seq 的用法正确吗？
我知道为多个并行伪随机数生成器 (PRNG) 播种的 3 种方法：
第一个选项
给定一个 seed，用 seed 初始化 PRNG 的第一个实例，用 seed+1 初始化第二个实例，等等。这里要注意的是状态如果种子未被散列，则 PRNG 最初将非常接近。一些 PRNG 需要很长时间才能发散。参见例如this blog post 获取更多信息。
但是，对于 std::mt19937 具体来说，这在我的测试中从来都不是问题，因为初始种子不是按原样获取而是得到“mangled/hashed”（比较 result_type constructor).所以这在实践中似乎是一个可行的选择。
但是，请注意，在使用单个 32 位整数为 Mersenne Twister（其内部状态为 624 个 32 位整数）播种时存在一些潜在的陷阱。例如，第一个数字永远不能是 7 或 13。有关详细信息，请参阅 this blog post。但是如果你不依赖于只抽取前几个数字的随机性而是从每个PRNG中抽取更合理数量的数字，那可能就没问题了。
第二个选项
没有std::seed_seq:
种子一个“父”PRNG。然后，初始化N个并行的PRNG，抽取N个随机数作为种子。这是你最初的想法，你抽取 2 个随机数 rng() 并初始化两个 std::mt19937:
std::mt19937 & rng = ...;
auto fooRNG = std::mt19937(rng()); // Seed a RNG with the output of `rng`.
auto barRNG = std::mt19937(rng());
这里要注意的主要问题是 birthday problem。它本质上表明，两次抽到相同数字的概率比您凭直觉想象的要大。给定一种取值范围为 b 的 PRNG（即 b 不同的值可以出现在其输出中），在绘制 [=23] 时绘制相同数字两次的概率 p(t) =] 人数可以估算为：
p(t) ~ t^2 / (2b) 对于 t^2 << b
（比较this post）。如果我们“稍微”延长估计值，只是为了说明基本问题：
对于生成 16 位整数的 PRNG，我们有 b=2^16。根据该公式，绘制 256 个数字有 50% 的机会绘制相同的数字两次。对于一个32位的PRNG（比如std::mt19937）我们需要绘制65536个数字，对于一个64位的整数PRNG我们需要绘制~4e9个数字才能达到50%。当然，这都是一个估计，所以你想得出比这少几个数量级的数字。另请参阅 this blog post 了解更多信息。
在使用此方法（32 位输出和输入！）为并行 std::m19937 实例播种的情况下，这意味着您可能不想绘制超过一百个左右的随机数。否则，您很有可能两次抽到相同的数字。当然，您可以通过保留已使用种子的列表来确保不会两次绘制相同的种子。或者使用 std::mt19937_64.
此外，对于 32 位数字的 Mersenne Twister 的播种，仍然存在上述潜在的陷阱。
带种子序列：
std::seed_seq 的想法是获取一些数字，“混合它们”，然后将它们作为 PRNG 的输入提供，以便它可以初始化其状态。由于 32 位 Mersenne Twister 具有 624 个 32 位整数的状态，因此您应该为种子序列提供那么多的数字以获得理论上的最佳结果。这样你就可以得到 b=2^(624*32)，这意味着你可以出于所有实际目的避免生日问题。
但在你的例子中
std::mt19937 fork(std::mt19937& rng) {
return std::mt19937(std::seed_seq({rng()}));
}
您只提供了一个 32 位整数。这实际上意味着您在将 32 位数字放入 std::mt19937 之前对其进行哈希处理。所以关于生日问题你不会有任何收获。额外的散列是不必要的，因为 std::mt19937 已经做了类似的事情。
std::seed_seq本身就有些瑕疵，参见this blog post。但我想出于实际目的，这并不重要。一个据称更好的替代方案 存在 ，但我没有使用它的经验。
第三个选项
一些 PRNG 算法，例如 PCG or xoshiro256++ 允许快速跳过大量随机数。例如，xoshiro256++ 在重复自身之前有 (2^256)-1 的周期。它允许向前跳转 2^128（或 2^192）个数字。所以这个想法是第一个 PRNG 被播种，然后你创建它的一个副本并向前跳 2^128 个数字，然后创建第二个 PRNG 的副本并再次向前跳 2^128，等等。所以每个实例在总范围 2^256 的长度为 2^128 的片段中工作。切片是随机独立的。这优雅地绕过了上述方法的问题。不幸的是，std::mt19937 不允许向前跳转。
补充说明
我发现 PRNG 出奇地难以“正确”使用。这实际上取决于用例，您需要多小心以及选择什么方法。想想如果出现问题，您的情况可能发生的最糟糕的事情，并投入相应的时间来研究该主题。
对于订单在科学模拟中，你只需要几十个左右的 std::mt19937 并行实例，我猜第一个和第二个选项（没有种子序列）都是可行的。但是如果你需要几百甚至更多，你就要慎重考虑了。
我正在使用 std::mt19937 生成确定性随机数。我想将它传递给函数，这样我就可以控制它们的随机源。我可以做 int foo(std::mt19937& rng);，但我想并行调用 foo 和 bar，所以这行不通。即使我将生成函数放在互斥锁后面（因此每次调用 operator() 都会执行 std::lock_guard lock(mutex); return rng();），并行调用 foo 和 bar 也不会是确定性的，因为互斥量竞争。
我觉得在概念上我应该能够做到这一点：
auto fooRNG = std::mt19937(rng()); // Seed a RNG with the output of `rng`.
auto barRNG = std::mt19937(rng());
parallel_invoke([&] { fooResult = foo(fooRNG); },
[&] { barResult = bar(barRNG); });
我在这里“分叉”rng 到两个具有不同种子的新的。由于 fooRNG 和 barRNG 是确定性播种的，因此它们应该是随机且独立的。
- 这个通用要点可行吗？
- 这个特定的实现是否足够（我怀疑）？
扩展问题：假设我想在一系列索引值上并行调用 baz(int n, std::mt19937&)，比如
auto seed = rng();
parallel_for(range(0, 1 << 20),
[&](int i) {
auto thisRNG = std::mt19937(seed ^ i); // Deterministically set up RNGs in parallel?
baz(i, thisRNG);
});
类似的东西应该有用，对吧？也就是说，只要我们给它足够的状态位？
更新：
查看 std::seed_seq，它看起来（？）像是旨在将不那么随机的种子变成高质量的种子：How to properly initialize a C++11 std::seed_seq
也许我想要的是
std::mt19937 fork(std::mt19937& rng) {
return std::mt19937(std::seed_seq({rng()}));
}
或更一般地说：
//! Represents a state that can be used to generate multiple
//! distinct deterministic child std::mt19937 instances.
class rng_fork {
std::mt19937::result_type m_seed;
public:
rng_fork(std::mt19937& rng) : m_seed(rng()) {}
// Copy is explicit b/c I think it's a correctness footgun:
explicit rng_fork(const rng_fork&) = default;
//! Make the ith fork: a deterministic but well-seeded
//! RNG based off the internal seed and the given index:
std::mt19937 ith_fork(std::mt19937::result_type index) const {
return std::mt19937(std::seed_seq({m_seed, index}));
}
};
那么初始示例将变为
auto fooRNG = fork(rng);
auto barRNG = fork(rng);
parallel_invoke([&] { fooResult = foo(fooRNG); },
[&] { barResult = bar(barRNG); });
和
auto fork_point = rng_fork{rng};
parallel_for(range(0, 1 << 20),
[&](int i) {
auto thisRNG = fork_point.ith_fork(i); // Deterministically set up a RNG in parallel.
baz(i, thisRNG);
});
std::seed_seq 的用法正确吗？
我知道为多个并行伪随机数生成器 (PRNG) 播种的 3 种方法：
第一个选项
给定一个 seed，用 seed 初始化 PRNG 的第一个实例，用 seed+1 初始化第二个实例，等等。这里要注意的是状态如果种子未被散列，则 PRNG 最初将非常接近。一些 PRNG 需要很长时间才能发散。参见例如this blog post 获取更多信息。
但是，对于 std::mt19937 具体来说，这在我的测试中从来都不是问题，因为初始种子不是按原样获取而是得到“mangled/hashed”（比较 result_type constructor).所以这在实践中似乎是一个可行的选择。
但是，请注意，在使用单个 32 位整数为 Mersenne Twister（其内部状态为 624 个 32 位整数）播种时存在一些潜在的陷阱。例如，第一个数字永远不能是 7 或 13。有关详细信息，请参阅 this blog post。但是如果你不依赖于只抽取前几个数字的随机性而是从每个PRNG中抽取更合理数量的数字，那可能就没问题了。
第二个选项
没有std::seed_seq:
种子一个“父”PRNG。然后，初始化N个并行的PRNG，抽取N个随机数作为种子。这是你最初的想法，你抽取 2 个随机数 rng() 并初始化两个 std::mt19937:
std::mt19937 & rng = ...;
auto fooRNG = std::mt19937(rng()); // Seed a RNG with the output of `rng`.
auto barRNG = std::mt19937(rng());
这里要注意的主要问题是 birthday problem。它本质上表明，两次抽到相同数字的概率比您凭直觉想象的要大。给定一种取值范围为 b 的 PRNG（即 b 不同的值可以出现在其输出中），在绘制 [=23] 时绘制相同数字两次的概率 p(t) =] 人数可以估算为：
p(t) ~ t^2 / (2b) 对于 t^2 << b
（比较this post）。如果我们“稍微”延长估计值，只是为了说明基本问题：
对于生成 16 位整数的 PRNG，我们有 b=2^16。根据该公式，绘制 256 个数字有 50% 的机会绘制相同的数字两次。对于一个32位的PRNG（比如std::mt19937）我们需要绘制65536个数字，对于一个64位的整数PRNG我们需要绘制~4e9个数字才能达到50%。当然，这都是一个估计，所以你想得出比这少几个数量级的数字。另请参阅 this blog post 了解更多信息。
在使用此方法（32 位输出和输入！）为并行 std::m19937 实例播种的情况下，这意味着您可能不想绘制超过一百个左右的随机数。否则，您很有可能两次抽到相同的数字。当然，您可以通过保留已使用种子的列表来确保不会两次绘制相同的种子。或者使用 std::mt19937_64.
此外，对于 32 位数字的 Mersenne Twister 的播种，仍然存在上述潜在的陷阱。
带种子序列：
std::seed_seq 的想法是获取一些数字，“混合它们”，然后将它们作为 PRNG 的输入提供，以便它可以初始化其状态。由于 32 位 Mersenne Twister 具有 624 个 32 位整数的状态，因此您应该为种子序列提供那么多的数字以获得理论上的最佳结果。这样你就可以得到 b=2^(624*32)，这意味着你可以出于所有实际目的避免生日问题。
但在你的例子中
std::mt19937 fork(std::mt19937& rng) {
return std::mt19937(std::seed_seq({rng()}));
}
您只提供了一个 32 位整数。这实际上意味着您在将 32 位数字放入 std::mt19937 之前对其进行哈希处理。所以关于生日问题你不会有任何收获。额外的散列是不必要的，因为 std::mt19937 已经做了类似的事情。
std::seed_seq本身就有些瑕疵，参见this blog post。但我想出于实际目的，这并不重要。一个据称更好的替代方案 存在 ，但我没有使用它的经验。
第三个选项
一些 PRNG 算法，例如 PCG or xoshiro256++ 允许快速跳过大量随机数。例如，xoshiro256++ 在重复自身之前有 (2^256)-1 的周期。它允许向前跳转 2^128（或 2^192）个数字。所以这个想法是第一个 PRNG 被播种，然后你创建它的一个副本并向前跳 2^128 个数字，然后创建第二个 PRNG 的副本并再次向前跳 2^128，等等。所以每个实例在总范围 2^256 的长度为 2^128 的片段中工作。切片是随机独立的。这优雅地绕过了上述方法的问题。不幸的是，std::mt19937 不允许向前跳转。
补充说明
我发现 PRNG 出奇地难以“正确”使用。这实际上取决于用例，您需要多小心以及选择什么方法。想想如果出现问题，您的情况可能发生的最糟糕的事情，并投入相应的时间来研究该主题。
对于订单在科学模拟中，你只需要几十个左右的 std::mt19937 并行实例，我猜第一个和第二个选项（没有种子序列）都是可行的。但是如果你需要几百甚至更多，你就要慎重考虑了。