生成一个不在已有 40 亿个整数中的整数。

Question

生成一个不在已有 40 亿个整数中的整数。

algorithmfilesearchout-of-memorymemory-limit

724

给我一个面试题：

假设有一个包含40亿个整数的输入文件，请提供一种算法，生成一个不包含在文件中的整数。假设你有1 GB内存。如果只有10 MB内存，你会怎么做？

我的分析：

文件的大小为4×10⁹×4字节=16 GB。

我们可以进行外部排序，这样可以让我们知道整数的范围。

我的问题是：在排序后的大整数集中检测缺失的整数的最佳方法是什么？

我的理解（阅读所有答案后）:

假设我们讨论的是32位整数，则有2³²= 40亿个不同的整数。

情况1：我们有1 GB = 10⁹ * 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⁶ * 8位 = 8000万个比特位

解决方案:

对于所有可能的16位前缀，有2¹⁶个整数=65536，我们需要2¹⁶ * 4 * 8 = 200万个比特位。我们需要构建65536个桶。对于每个桶，我们需要4个字节来保存所有可能性，因为最坏的情况是所有40亿个整数属于同一个桶。

通过第一次文件遍历，建立每个桶的计数器。

扫描桶，找到第一个少于65536个命中的桶。

通过文件的第二次遍历，构建新的桶，其高16位前缀与步骤2中发现的相同。

扫描步骤3中构建的桶，找到第一个没有命中的桶。

代码与上面的代码非常相似。

结论：通过增加文件遍历次数来减少内存使用。

^{针对晚来者的澄清：问题在提问时没有明确说明文件中只有一个整数没有出现。至少大多数人不是这样理解的。评论线程中的许多评论都涉及该任务的变体。不幸的是，介绍这个变体的评论后来被其作者删除了，所以现在看起来像是它的孤儿回复误解了一切。非常抱歉，这很令人困惑。}

- SecureFish

33

@trashgod，你错了。对于4294967295个唯一整数，你将剩下1个整数。为了找到它，你需要对所有整数求和，然后从所有可能整数的预计总和中减去它。 - Nakilon

58

这是来自《编程珠玑》的第二个“珠子”，我建议您阅读书中的整个讨论。请参阅http://books.google.com/books?id=kse_7qbWbjsC&lpg=PP1&pg=PA11#v=onepage&q&f=false。 - Alok Singhal

9

一个64位整数已经足够大了。 - cftarnas

82

获取缺失数字的函数：

int getMissingNumber(File inputFile)
{
    return 4;
}

（参考资料：http://xkcd.com/221/） - johnny

16

即使你无法在1到2的32次方之间存储所有整数的总和，在像C/C++这样的语言中，整数类型始终保留结合律和交换律等特性，这并不重要。这意味着，尽管总和可能不是正确的答案，但如果您计算了有溢出的期望值、有溢出的实际总和，然后相减，结果仍然是正确的（前提是本身没有溢出）。 - thedayturns

显示剩余34条评论

38个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Gibson · Answer 1

2

如果您不考虑32位的限制，只需返回一个随机生成的64位数字（如果您是悲观主义者，则为128位）。碰撞的概率为1 in 2^64/(4*10^9) = 4611686018.4（大约为40亿分之1）。大多数情况下，您都是正确的！（开个玩笑...有点。）

- Peter Gibson

我看到这个已经被建议了 :) 给那些人点赞 - Peter Gibson

生日悖论使得这种解决方案不值得冒险，如果没有检查文件以确定您的随机猜测是否实际上是一个有效答案。(在这种情况下，生日悖论并不适用，但是反复调用此函数以生成新的唯一值确实会产生生日悖论情况。) - Peter Cordes

@PeterCordes 随机生成的128位数字正是UUID的工作原理——在维基百科UUID页面中，当计算碰撞概率时，它们甚至提到了生日悖论。 - Peter Gibson

变量：在集合中找到最大值，加1。 - Phil

我会使用快速排序算法对原始数组进行排序（不需要额外的存储空间），然后遍历整个数组并报告第一个“跳过”的整数。搞定了。问题已回答。 - Level 42

- hacksoncode · Answer 2

也许我完全没有理解这个问题的重点，但是您想要在一个已经排序的整数文件中找到一个缺失的整数？

嗯...真的吗？让我们考虑一下这样的文件会是什么样子：

1 2 3 4 5 6 ... 第一个缺失的数字 ... 等等。

这个问题的解决方案似乎很简单。

- Lucas Membrane · Answer 3

你不需要对它们进行排序，只需重复划分它们的子集。

第一步就像快速排序的第一次遍历。选择一个整数x，并使用它通过数组进行一次遍历，将所有小于x的值放在其左侧，将大于x的值放在其右侧。找出x的哪一侧有最多的可用插槽（不在列表中的整数）。这可以通过比较x的值与其位置来轻松计算。然后在x的那一侧的子列表上重复划分。然后在具有最多可用整数的子子列表上重复划分，等等。将总比较次数降至空范围应该约为40亿，加减误差。

- w00t · Answer 4

你可以通过在某些树结构中存储未访问整数的范围来加速查找缺失的整数。

你可以从存储[0..4294967295]开始，每次读取一个整数时，就将其所在的范围拆分，当范围为空时删除该范围。最终，你将得到确切缺失的整数集合。因此，如果你看到第一个整数是5，那么你将得到[0..4]和[6..4294967295]。

这比标记位慢得多，因此只适用于10MB情况，前提是你可以将树的较低级别存储在文件中。

存储这样一棵树的一种方法是使用B树，以范围的起始为键，以范围的结束为值。最坏情况下，当你获取所有奇数或偶数整数时，意味着需要存储2^31个值或数十GB的树...痛苦。最好的情况是一个排序的文件，你只需要为整个树使用几个整数。

所以这并不是正确的答案，但我想提一下这种方法。我想我会失败的面试；-）

- Timofey · Answer 5

我想出了以下算法。

我的想法是：遍历整个整数文件一次，并对每个位位置的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是一个负数，因此，(long)1<<31是正确的做法

- Sib · Answer 6

我可能读得太仔细了，但问题说“生成一个不包含在文件中的整数”。我只需对列表进行排序并将1添加到最大条目即可。瞬间，就有了一个不包含在文件中的整数。

- benjist · Answer 7

虽然这是一个老问题，但我对“非功能性”要求感到好奇。在我看来，应该给出一些提示——如果这个问题不是在一本书中提出的，而是在其他地方提出的，然后继续讨论所有可能性及其优缺点。通常情况下，它似乎是在面试中问的，这让我感到困惑，因为如果不知道软件需求，即“它必须非常快速地查找丢失的数字，因为它每秒钟使用x次”，就无法给出明确的答案。

我认为这样的问题可能可以给出合理的答案。

我会将所有数字归并排序到一个新文件中，每个int使用4个字节。当然，这一开始会很慢。但是可以用很少的内存量完成（您不需要必须全部保存在RAM中）
使用二分查找检查数字是否存在于预排序文件中。由于我们保留每个值的4个字节，因此这不是问题

缺点：

文件大小
第一次排序很慢——但只需要一次

优点：

查找非常快速

所以，这是一本非常好的问题。但是我认为，在问题没有完全被了解的情况下，询问单一最佳解决方案是一个奇怪的问题。

- Russell Clarke · Answer 8

当然，只是有限的经验（刚开始在大学学习Java），您可以运行一组（桶）int，如果未找到数字则处理该桶。这将释放空间并通过每个数据单元运行检查。如果找到所需内容，则将其添加到计数变量中。需要很长时间，但是，如果为每个部分制作多个变量，并使检查计数通过每个变量并确保它们同时退出/处理，变量存储应不会增加？并且将加速检查过程。只是一个想法。

生成一个不在已有 40 亿个整数中的整数。

我的分析：

我的理解（阅读所有答案后）:

情况1：我们有1 GB = 109 * 8位 = 80亿位的内存。

解决方案：

实现：

情形2: 10 MB内存 = 10 * 106 * 8位 = 8000万个比特位

解决方案:

情况1：我们有1 GB = 10⁹ * 8位 = 80亿位的内存。

情形2: 10 MB内存 = 10 * 10⁶ * 8位 = 8000万个比特位