最大化区域中唯一随机数的数量

Question

我正在尝试使用 mt19937 引擎和 std：：random_device 作为种子源生成均匀分布的随机数。如果我幸运的话，我会从 40 亿个可能的值中获得几十万个唯一数字。我想知道它是否可以比这更好。

我尝试使用高分辨率计时器增加熵，而使用 seed_seq (https://stackoverflow.com/a/34493057/5852409) 的随机设备也尝试初始化 mt19937 (https://codereview.stackexchange.com/a/109266) 的所有 624 种状态。但是，没有看到任何改善。

#include <random>
#include <iostream>
#include <set>
void main()
{
std::random_device rd;
std::mt19937 engn(rd());
std::uniform_int_distribution<unsigned int> unidist(0, 0xFFFFFFFF - 1);
std::set<unsigned int> s;
auto itr = s.insert(unidist(engn));
int k = 0;
while (itr.second)
{
itr = s.insert(unidist(engn));
k++;
}
std::cout << k << 'n';
}

Answer 1

首先，确保您了解生日悖论。 即，您在大约一万个或十万个数字之后获得重复项的事实并不表示mt19937存在统计缺陷。

作为由于这个悖论的粗略估计，即使对于一个完美的随机生成器，在大约 2^16 = 65536 个值之后，重复也可能在可能值的平方根之后变得可能。

其次，请注意，熵并不意味着输出的唯一性。想象一下，将一个完全公平的 100 面骰子扔 100 次。至少一个值出现两次的可能性实际上远大于每个值只出现一次的可能性。熵是系统中状态数的度量。在您的情况下，熵与种子的质量(涵盖 PRNG 的许多不同初始状态)有关，而不是输出的唯一性。

第三，如果你有一个用例，你必须确保唯一性(例如ID或句柄)，但你需要较差的可预测性，也就是随机性，你基本上有两个选择：

• 存储"采取"值并根据需要"重新滚动"。还有一些概率算法可以检测具有更少RAM的重复项，但误报的可能性很小。
• 使用更大的 - 超过两倍的位 - 处理空间，并希望不会发生冲突。当偶尔的碰撞是不必要的，但造成的伤害有限时，例如导致理论上不必要的昂贵重新计算，这是合适的。