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

Question

假设我有一个取32位整数的函数,并返回随机的32位整数.

现在,我想看看这个函数将在0到2 ^ 32-1之间的所有可能输入值上返回多少和哪些重复值.如果我有超过4gig的免费ram,我可以让这很容易,但我没有超过1gig ram.

我尝试使用4gig文件将计算值映射到磁盘上,其中一个字节表示它已经获得了多少重复,但我注意到将来我的硬盘速度将近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个条目.如果地图变得太大而无法一次保留在内存中,则可以对其进行分区,即仅允许特定范围内的值,即整个数字空间的四分之一.如果重复数据的分布相当均匀,这将使地图仅占整个地图大小的1/4.您当然需要每季度运行该程序4次以查找所有重复项.

要查找第一个副本,您可以在两个过程中运行它:在第一个过程中,您使用位图查找重复项并将它们放入地图中.在第二遍中,如果地图中已有条目且值尚未存在,则跳过位图并将值添加到地图中.

不,没有理由在无符号的int数组上使用int.你也可以使用unsigned int,这实际上更合适.