我的面试问题是这样的:
给定一个包含40亿个整数的输入文件，提供一种算法来生成一个文件中不包含的整数。假设您有1gb内存。如果你只有10mb的内存，你会怎么做。
我的分析:
文件大小为4×109×4 bytes = 16gb。
我们可以进行外部排序，从而知道整数的范围。
我的问题是，在已排序的大整数集中检测缺失整数的最佳方法是什么?
我的理解(看完所有答案后):
假设我们讨论的是32位整数，有232 = 4*109个不同的整数。
情况1:我们有1gb = 1 * 109 * 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);
}
}
}
情形二:10mb内存= 10 * 106 * 8bits = 8000万bits
Solution:
For all possible 16-bit prefixes, there are 216 number of
integers = 65536, we need 216 * 4 * 8 = 2 million bits. We need build 65536 buckets. For each bucket, we need 4 bytes holding all possibilities because the worst case is all the 4 billion integers belong to the same bucket.
Build the counter of each bucket through the first pass through the file.
Scan the buckets, find the first one who has less than 65536 hit.
Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
Scan the buckets built in step3, find the first bucket which doesnt
have a hit.
The code is very similar to above one.
结论:
我们通过增加文件传递来减少内存。
为那些迟到的人澄清一下:这个问题，正如所问的，并不是说有一个整数没有包含在文件中——至少大多数人不是这么理解的。不过，评论线程中的许多评论都是关于任务的变化。不幸的是，把它引入评论线程的评论后来被它的作者删除了，所以现在看起来它的孤儿回复只是误解了一切。这很让人困惑，抱歉。
一些消除
一种方法是消除比特，但这实际上可能不会产生结果(很可能不会)。Psuedocode:
long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
val = val & ~fileVal;
if (val == 0) error;
}
位计数
跟踪比特数;用最少的比特来产生一个值。同样，这也不能保证生成正确的值。
范围的逻辑
跟踪列表的顺序范围(按开始顺序)。范围由结构定义:
struct Range
{
long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };
遍历文件中的每个值，并尝试将其从当前范围中删除。这个方法没有内存保证，但是它应该做得很好。
The simplest approach is to find the minimum number in the file, and return 1 less than that. This uses O(1) storage, and O(n) time for a file of n numbers. However, it will fail if number range is limited, which could make min-1 not-a-number.
The simple and straightforward method of using a bitmap has already been mentioned. That method uses O(n) time and storage.
A 2-pass method with 2^16 counting-buckets has also been mentioned. It reads 2*n integers, so uses O(n) time and O(1) storage, but it cannot handle datasets with more than 2^16 numbers. However, it's easily extended to (eg) 2^60 64-bit integers by running 4 passes instead of 2, and easily adapted to using tiny memory by using only as many bins as fit in memory and increasing the number of passes correspondingly, in which case run time is no longer O(n) but instead is O(n*log n).
The method of XOR'ing all the numbers together, mentioned so far by rfrankel and at length by ircmaxell answers the question asked in stackoverflow#35185, as ltn100 pointed out. It uses O(1) storage and O(n) run time. If for the moment we assume 32-bit integers, XOR has a 7% probability of producing a distinct number. Rationale: given ~ 4G distinct numbers XOR'd together, and ca. 300M not in file, the number of set bits in each bit position has equal chance of being odd or even. Thus, 2^32 numbers have equal likelihood of arising as the XOR result, of which 93% are already in file. Note that if the numbers in file aren't all distinct, the XOR method's probability of success rises.
好的，这并没有经过充分的思考，因为它假设文件中的整数遵循某种静态分布。显然他们不需要这样做，但即使这样，也应该试试这个:
有≈43亿个32位整数。我们不知道它们在文件中是如何分布的，但最糟糕的情况是具有最高香农熵的情况:均匀分布。在这种情况下，任何一个整数不出现在文件中的概率为
((2³²-1)/2³²)⁰⁰⁰⁰≈.4
The lower the Shannon entropy, the higher this probability gets on the average, but even for this worst case we have a chance of 90% to find a nonoccurring number after 5 guesses with random integers. Just create such numbers with a pseudorandom generator, store them in a list. Then read int after int and compare it to all of your guesses. When there's a match, remove this list entry. After having been through all of the file, chances are you will have more than one guess left. Use any of them. In the rare (10% even at worst case) event of no guess remaining, get a new set of random integers, perhaps more this time (10->99%).
内存消耗:几十个字节，复杂度:O(n)，开销:neclectable，因为大部分时间将花费在不可避免的硬盘访问上，而不是比较int类型。
当我们不假设静态分布时，实际最坏的情况是每个整数都出现最大值。曾经，因为那时只有
1 - 4000000000/2³²≈6%
所有的整数都不会出现在文件中。因此，您需要更多的猜测，但这仍然不会消耗大量的内存。
