我收到了这个面试问题:
给定一个具有 40 亿个整数的输入文件,提供一个算法来生成一个不包含在文件中的整数。假设您有 1 GB 内存。跟进如果您只有 10 MB 的内存,您会做什么。
我的分析:
文件大小为 4×10 9 ×4 字节 = 16 GB。
我们可以进行外部排序,从而让我们知道整数的范围。
我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么?
我的理解(阅读所有答案后):
假设我们谈论的是 32 位整数,则有 2 32 = 4*10 9 个不同的整数。
案例 1:我们有 1 GB = 1 * 10 9 * 8 位 = 80 亿位内存。
解决方案:
如果我们使用一位代表一个不同的整数,就足够了。我们不需要排序。
执行:
int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
Scanner in = new Scanner(new FileReader("a.txt"));
while(in.hasNextInt()){
int n = in.nextInt();
bitfield[n/radix] |= (1 << (n%radix));
}
for(int i = 0; i< bitfield.lenght; i++){
for(int j =0; j<radix; j++){
if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
}
}
}
情况 2:10 MB 内存 = 10 * 10 6 * 8 位 = 8000 万位
解决方案:
对于所有可能的 16 位前缀,有 2 16个整数 = 65536,我们需要 2 16 * 4 * 8 = 2 百万位。我们需要构建 65536 个存储桶。对于每个桶,我们需要 4 个字节来保存所有可能性,因为最坏的情况是所有 40 亿个整数都属于同一个桶。
- 通过文件的第一次遍历构建每个桶的计数器。
- 扫描桶,找到第一个命中少于 65536 的桶。
- 构建新的存储桶,其高 16 位前缀是我们在第 2 步到文件的第二遍中找到的
- 扫描step3构建的bucket,找到第一个没有命中的bucket。
代码与上面的代码非常相似。
结论:我们通过增加文件传递来减少内存。
对迟到的人的澄清:问题,正如所问的,并不是说文件中不包含确切的一个整数——至少大多数人不是这样解释的。不过,评论线程中的许多评论都是关于该任务的变体。不幸的是,将它引入评论线程的评论后来被其作者删除,所以现在看起来对它的孤立回复只是误解了一切。非常混乱,抱歉。