低内存内存管理:查找和跟踪随机函数返回值的重复项

Question

假设我有一个函数，它接受 32 位整数输入，并返回随机的 32 位整数输出。

现在，我想看看这个函数将在从 0 到 2^32-1 的所有可能的输入值上返回多少个重复值。如果我有超过 4GB 的免费内存，我可以让这变得容易，但我的内存不超过 1g。

我尝试使用 4gig 文件在磁盘上映射计算值，其中一个字节表示它获得了多少重复项，但我注意到以我的 HDD 速度，近似的完成时间将是未来 25 天！（我不得不使用SSD，因为害怕损坏我的硬盘...

所以，现在下一步是在 RAM 中计算这一切，根本不使用磁盘，但是在思考如何优雅地解决这个问题时，我跑了起来。我能想到的唯一方法是循环 （2^32）*（2^32） 乘以函数，但这显然比我的 HDD 方法还要慢。

我现在需要的是一些讨厌的想法来加快速度！

编辑：该函数并不是真正的随机函数，而是类似于随机函数，但事实是您不需要了解该函数的任何信息，这不是这里的问题。我想用我的肉眼看到所有的重复项，而不仅仅是一些数学猜测可能有多少。我为什么要这样做？出于好奇:)

Answer 1

要检查 2^32 个可能的重复项，您只需要 4 千兆位，即 512MB，因为每个值只需要一个位。第一次点击零位将其设置为 1，每次点击 1 位时，您就知道您有一个副本，可以将其打印出来或对它做任何您想做的事情。

也就是说，您可以执行以下操作：

int value = nextValue(...);
static int bits[] = new int[ 0x08000000 ]();
unsigned int idx = value >> 5, bit = 1 << ( value & 31 );
if( bits[ idx ] & bit )
   // duplicate
else
    bits[ idx ] |= bit;

回应您的意见

是的，如果重复项不是太多，也没有太多不同的重复项，则将重复项放入地图中是个好主意。这里最坏的情况是 2^31 个条目，如果每 2 个值恰好出现两次。如果映射变得太大而无法立即保存在内存中，您可以对其进行分区，即只允许特定范围内的值，即整个数字空间的四分之一。如果重复项分布相当均匀，这将使地图的大小仅为整个地图的 1/4。当然，您需要每个季度运行该程序 4 次才能找到所有重复项。

要查找第一个重复项，您可以分两次运行它：在第一遍中，您使用位图查找重复项并将它们放入图中。在第二遍中，如果映射中已经有一个条目并且该值尚不存在，则跳过位图并将值添加到映射中。

不，没有充分的理由在无符号的 int 数组上使用 int。 您也可以使用无符号的 int，这实际上在这里更合适。

Answer 2

一个不可问的问题：为什么？. 你想实现什么目标？

这是某种蒙特卡洛实验吗？

如果没有，只需查找您的（P）RNG的实现算法，它将准确地告诉您值的分布

。

看看Boost.Random，寻找比你所能想象的更多的选择，它会有例如 uniform_int<>和变量生成器，可以限制输出范围，同时仍对输出域中的值分布有明确定义的保证