编程珍珠:找到一个整数至少出现两次

Question

它在2.6节和问题2中,原始问题是这样的:

"鉴于包含4,300,000,000个32位整数的顺序文件,你怎么能找到至少出现两次的整数？"

我对这个练习的问题是:上述问题的技巧是什么？这个问题在于什么样的通用算法类别？

Answer 1

创建一个长度为2 ^ 32位(初始化为零)的位数组,大约为512MB,适用于任何现代机器的RAM.

开始读取文件,int by int,用与int值相同的索引检查位,如果设置了位,则发现重复,如果为零,则设置为1并继续执行文件中的下一个int .

诀窍是找到合适的数据结构和算法.在这种情况下,一切都适合RAM,具有合适的数据结构,可以使用简单有效的算法.
如果数字是int64,则需要找到合适的排序策略或进行多次传递,具体取决于您可用的额外存储量.

Answer 2

鸽笼原则 - 如果你在M鸽笼中有N只鸽子,并且N> M,那么在一个洞中至少有2只鸽子.这组32位整数是我们的2 ^ 32个鸽笼,我们文件中的43亿个数字是鸽子.从4.3x10 ^ 9> 2 ^ 32,我们知道有重复.

您可以应用此原则来测试我们正在查找的副本是否在数据的子集中,而不是以读取整个文件为代价,而不是一次只加载到RAM中 - 只计算次数您在测试范围内看到一个数字,并与该范围内的整数总数进行比较.例如,检查1,000,000到2,000,000之间的重复项:

int pigeons = 0;
int pigeonholes = 2000000 - 1000000 + 1; // include both fenceposts
for (each number N in file) {
  if ( N >= 1000000 && N <= 2000000 ) {
    pigeons++
  }
}
if (pigeons > pigeonholes) {
  // one of the duplicates is between 1,000,000 and 2,000,000
  // try again with a narrower range
} 

选择要检查的范围有多大以及要读取16GB数据的次数取决于您:)

就一般算法类别而言,这是一个组合学(关于计数的数学)问题.