我的面试问题是这样的:

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

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


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


当前回答

也许我完全没有理解这个问题的重点,但是您想从一个已排序的整数文件中找到一个丢失的整数吗?

喔…真的吗?让我们想想这样的文件会是什么样子:

1 2 3 4 5 6…第一个丢失的号码……等。

这个问题的解决办法似乎微不足道。

其他回答

关于这个问题的详细讨论已经在Jon Bentley的“第一栏”中讨论过。“编程珍珠”Addison-Wesley第3-10页

Bentley讨论了几种方法,包括外部排序,使用几个外部文件的归并排序等,但Bentley建议的最佳方法是使用位字段的单次传递算法,他幽默地称之为“神奇排序”:) 来看看这个问题,40亿个数字可以表示为:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

实现bitset的代码很简单:(取自解决方案页面)

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

Bentley的算法只对文件进行一次传递,在数组中设置适当的位,然后使用上面的测试宏检查这个数组以找到缺失的数字。

如果可用内存小于0.466 GB, Bentley建议使用k-pass算法,根据可用内存将输入划分为不同的范围。举一个非常简单的例子,如果只有1个字节(即处理8个数字的内存)可用,并且范围从0到31,我们将其分为0到7、8-15、16-22等范围,并在每次32/8 = 4次传递中处理这个范围。

HTH.

使用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数字-但内存需求不会改变。

对于10mb内存限制:

将数字转换为二进制表示形式。 创建一个二叉树,其中左= 0,右= 1。 使用二进制表示将每个数字插入树中。 如果已经插入了一个数字,则叶子将已经创建。

完成后,只需使用之前未创建的路径来创建所请求的数字。

40亿数字= 2^32,这意味着10 MB可能不够。

EDIT

优化是可能的,如果已经创建了两个末端叶并且有一个共同的父级,那么可以将它们删除,并且父级标记为不是解决方案。这减少了分支,减少了对内存的需求。

编辑II

没有必要完全构建树。只有在数字相似的情况下才需要构建深度分支。如果我们也砍掉树枝,那么这个解决方案实际上可能有效。

根据原题中目前的措辞,最简单的解决方法是:

找到文件中的最大值,然后加上1。

好的,这并没有经过充分的思考,因为它假设文件中的整数遵循某种静态分布。显然他们不需要这样做,但即使这样,也应该试试这个:


有≈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% 所有的整数都不会出现在文件中。因此,您需要更多的猜测,但这仍然不会消耗大量的内存。