我的面试问题是这样的:

给定一个包含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.

结论: 我们通过增加文件传递来减少内存。


为那些迟到的人澄清一下:这个问题,正如所问的,并不是说有一个整数没有包含在文件中——至少大多数人不是这么理解的。不过,评论线程中的许多评论都是关于任务的变化。不幸的是,把它引入评论线程的评论后来被它的作者删除了,所以现在看起来它的孤儿回复只是误解了一切。这很让人困惑,抱歉。


当前回答

我认为这是一个已解决的问题(见上文),但还有一个有趣的情况需要记住,因为它可能会被问到:

如果恰好有4,294,967,295(2^32 - 1)个没有重复的32位整数,因此只有一个缺失,有一个简单的解决方案。

从0开始计算运行总数,对于文件中的每个整数,将该整数加上32位溢出(实际上,runningTotal = (runningTotal + nextInteger) % 4294967296)。一旦完成,将4294967296/2加到运行总数中,同样是32位溢出。用4294967296减去这个,结果就是缺少的整数。

“只缺少一个整数”的问题只需运行一次就可以解决,并且只有64位RAM专用于数据(运行总数为32位,读入下一个整数为32位)。

推论:如果我们不关心整数结果必须有多少位,那么更通用的规范非常容易匹配。我们只是生成一个足够大的整数,它不能包含在我们给定的文件中。同样,这只占用极小的RAM。请参阅伪代码。

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

其他回答

这是个陷阱问题,除非引用不当。只需要通读文件一次,得到最大整数n,并返回n+1。

当然,您需要一个备份计划,以防n+1导致整数溢出。

我想出了下面的算法。

我的想法是:遍历整个整数文件一次,对每个位位置数0和1。0和1的数量必须是2^(numOfBits)/2,因此,如果数量比预期的少,我们可以使用我们的结果数。

例如,假设整数是32位,那么我们需要

int[] ones = new int[32];
int[] zeroes = new int[32];

对于每个数字,我们必须迭代32位,并增加0或1的值:

for(int i = 0; i < 32; i++){
   ones[i] += (val>>i&0x1); 
   zeroes[i] += (val>>i&0x1)==1?0:1;
}

最后,在文件处理后:

int res = 0;
for(int i = 0; i < 32; i++){
   if(ones[i] < (long)1<<31)res|=1<<i;
}
return res;

注意:在某些语言中(如Java) 1<<31是负数,因此,(长)1<<31是正确的方法

使用BitSet。40亿个整数(假设最多2^32个整数)以每字节8个的速度打包到BitSet中,大约是2^32 / 2^3 = 2^29 = 0.5 Gb。

要添加更多的细节-每次读取一个数字时,在BitSet中设置相应的位。然后,遍历BitSet以找到第一个不存在的数字。事实上,你可以通过重复选择一个随机数并测试它是否存在来有效地做到这一点。

实际上BitSet.nextClearBit(0)会告诉你第一个非设置位。

看看BitSet API,它似乎只支持0..MAX_INT,所以你可能需要2个bitset -一个用于+ ve数字,一个用于- ve数字-但内存需求不会改变。

您可以使用位标志来标记一个整数是否存在。

遍历整个文件后,扫描每个位以确定数字是否存在。

假设每个整数是32位,如果进行了位标记,它们将方便地放入1gb RAM中。

If they are 32-bit integers (likely from the choice of ~4 billion numbers close to 232), your list of 4 billion numbers will take up at most 93% of the possible integers (4 * 109 / (232) ). So if you create a bit-array of 232 bits with each bit initialized to zero (which will take up 229 bytes ~ 500 MB of RAM; remember a byte = 23 bits = 8 bits), read through your integer list and for each int set the corresponding bit-array element from 0 to 1; and then read through your bit-array and return the first bit that's still 0.

In the case where you have less RAM (~10 MB), this solution needs to be slightly modified. 10 MB ~ 83886080 bits is still enough to do a bit-array for all numbers between 0 and 83886079. So you could read through your list of ints; and only record #s that are between 0 and 83886079 in your bit array. If the numbers are randomly distributed; with overwhelming probability (it differs by 100% by about 10-2592069) you will find a missing int). In fact, if you only choose numbers 1 to 2048 (with only 256 bytes of RAM) you'd still find a missing number an overwhelming percentage (99.99999999999999999999999999999999999999999999999999999999999995%) of the time.

但我们假设不是有40亿个数字;你有232 - 1这样的数字和不到10mb的RAM;所以任何小范围的整数都只有很小的可能性不包含这个数字。

如果保证列表中的每个int都是唯一的,那么可以将这些数字相加,并减去一个#,再减去完整的和(½)(232)(232 - 1)= 9223372034707292160,以找到缺少的int。但是,如果出现了两次int,则此方法将失败。

However, you can always divide and conquer. A naive method, would be to read through the array and count the number of numbers that are in the first half (0 to 231-1) and second half (231, 232). Then pick the range with fewer numbers and repeat dividing that range in half. (Say if there were two less number in (231, 232) then your next search would count the numbers in the range (231, 3*230-1), (3*230, 232). Keep repeating until you find a range with zero numbers and you have your answer. Should take O(lg N) ~ 32 reads through the array.

这种方法效率很低。我们在每一步中只使用两个整数(或者大约8字节的RAM和一个4字节(32位)整数)。更好的方法是将其划分为sqrt(232) = 216 = 65536个箱子,每个箱子中有65536个数字。每个bin需要4个字节来存储它的计数,因此需要218字节= 256 kB。因此,bin 0为(0 ~ 65535=216-1),bin 1为(216=65536 ~ 2*216-1=131071),bin 2为(2*216=131072 ~ 3*216-1=196607)。在python中,你会有这样的代码:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

通读~ 40亿整数列表;然后计算216个容器中每个容器中有多少int,并找到一个不包含65536个数字的incomplete_bin。然后你再读一遍40亿的整数列表;但这次只注意整数在这个范围内;当你找到他们的时候,你会有点抓狂。

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break