生成一个不在已有 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 提供, 点击上面的

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

- Paul · Answer 1

19

他们可能正在寻找您是否听说过一种概率性的布隆过滤器，它可以非常高效地确定一个值是否不是一个大集合的一部分（但只能以高概率确定它是集合的成员）。

- Paul

5

如果 Bloom Filter 中设置的可能值超过了90％，那么它很可能会退化为类似其他答案中使用的位图。否则，您最终将得到一个毫无用处的完全填满的位串。 - Christopher Creutzig

@Christopher 我对Bloom过滤器的理解是，直到达到100％才会获得填充的比特数组。 - Paul

否则，您将得到错误的负面结果。 - Paul

1

@Paul，填充的位数组会产生允许的误报。在这种情况下，布隆过滤器很可能会退化为解决方案返回假阳性的情况。 - ataylor

2

@Paul：只要哈希函数的数量乘以条目数等于字段长度，您就可以立即获得填充的位数组。当然，那将是一个特殊情况，但概率会很快上升。 - Christopher Creutzig

- oosterwal · Answer 2

17

根据原问题的表述，最简单的解决方案是：

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

- oosterwal

5

如果文件中包含了最大整数，会怎么样？ - Petr Peller

@Petr Peller：一个BIGINT库本质上会消除整数大小的限制。 - oosterwal

2

@oosterwal，如果允许这个答案，那么你甚至不需要读取文件——只需打印尽可能大的数字即可。 - Nakilon

1

@oosterwal，如果您的随机大数是您可以打印的最大值，并且它在文件中，则无法解决此任务。 - Nakilon

3

收到您的意见。大致上相当于计算文件中数字的总数，并打印出具有相同位数的数字。 - oosterwal

显示剩余2条评论

- dty · Answer 3

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

- vsz · Answer 4

如果文件大小没有限制，最快的方法是获取文件长度并生成相同长度+1的随机数字（或只是"11111..."）。优点：您甚至不需要读取文件，并且可以将内存使用几乎降为零。缺点：您将打印数十亿个数字。

然而，如果唯一的因素是最小化内存使用，而其他任何因素都不重要，这将是最优解。这甚至可能会使你获得“滥用规则最严重”的奖项。

- ircmaxell · Answer 5

如果我们假设数字范围始终为2^n（2的偶次幂），那么异或运算将起作用（如另一位用户所示）。至于为什么，让我们来证明一下：

理论：对于任何具有2^n个元素并且缺少一个元素的以0为基础的整数范围，只需将已知值进行异或运算即可得出缺失的数字。

证明：我们来看n=2的情况。对于n=2，我们可以表示4个唯一的整数：0、1、2、3。它们的位模式为：

0 - 00 1 - 01 2 - 10 3 - 11

现在，如果我们看一下，每一位都恰好设置了两次。因此，由于它被设置了偶数次，数字的异或将产生0。如果缺少一个数字，则异或将产生一个数字，当该数字和缺失的数字进行异或运算时，结果为0。因此，缺失的数字和结果的异或数字完全相同。如果我们移除2，则结果的异或将是10（或2）。

现在，我们来看看n + 1的情况。让我们将n中每个位设置的次数称为x，n+1中每个位设置的次数称为y。y的值将等于y = x * 2，因为有x个元素的n+1位设置为0，有x个元素的n+1位设置为1。由于2x始终是偶数，因此n + 1将始终将每个位设置为偶数次。

因此，既然n=2有效，n+1也有效，则异或方法对所有n≥2的值都有效。

基于0的范围的算法：这很简单。它使用2*n位内存，因此对于小于等于32的任何范围，2个32位整数将起作用（忽略文件描述符消耗的任何内存）。它只需要一遍遍历文件即可完成。

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

任意进制范围的算法

只要范围总数是2^n，这个算法就适用于从任意起始数到任意结束数的范围。它基本上会重新将范围的最小值设为0。但是它需要通过文件进行两次传递（第一次获取最小值，第二次计算缺失的整数）。

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

任意范围

我们可以使用这种修改后的方法来处理一组任意范围，因为所有范围都至少会穿过一个2^n的幂。这仅适用于存在单个丢失位的情况。它需要对未排序的文件进行两次遍历，但每次总能找到单个丢失的数字：

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

该函数将数据范围重新基于0，并计算异或时需要追加的未排序值数量。添加一个缺失的值（计数缺失的那个值），并不断对n值进行异或，每次增加1，直到n是2的幂为止。然后将结果重新基于原始基数。完成。

以下是我在PHP中测试过的算法示例（使用数组而不是文件，但概念相同）：

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

将任意范围的值组成一个数组（我测试了包括负数），其中缺少一个值，每次它都能找到正确的值。

另一种方法

既然我们可以使用外部排序，为什么不检查间隙呢？如果假设在运行此算法之前文件已经排序：

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

- Mark Ransom · Answer 6

这是一个骗人的问题，除非它被错误地引用。只需阅读一次文件以获取最大整数n，然后返回n+1。当然，如果n+1导致整数溢出，您需要备份计划。

- Justin Morgan · Answer 7

检查输入文件的大小，然后输出任何一个数字，该数字太大而无法被该文件大小所表示。这可能看起来像是一个廉价的技巧，但它是一个面试问题的创造性解决方案，它巧妙地避开了内存问题，并且在技术上是O(n)。

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

应该打印10的二进制位数次方减1，它总是大于2的二进制位数次方。严格来说，你需要超过的数字是2的二进制位数次方减去（4 * 10的九次方减1），因为你知道文件中还有（40亿减1）其他整数，并且即使进行完美压缩，它们至少会占用一个比特位。

- James Waldby - jwpat7 · Answer 8

最简单的方法是在文件中找到最小的数字，并返回比它小1的数。这种方法使用O(1)的存储空间和O(n)的时间处理n个数字的文件。然而，如果数字范围受限，最小值减1可能不是一个数字。

使用位图的简单直接方法已经被提到过了。该方法使用O(n)的时间和存储空间。

还提到了一种使用2^16计数桶的双通道方法。它读取2*n个整数，因此使用O(n)的时间和O(1)的存储空间，但无法处理超过2^16个数字的数据集。然而，它可以通过运行4次而不是2次来轻松扩展到(例如)2^60个64位整数，并且可以通过只使用适合内存的数量的bin并相应地增加传递数量来轻松适应使用微小内存的情况，在这种情况下，运行时间不再是O(n)，而是O(n*log n)。

目前由rfrankel和ircmaxell详细介绍的XOR所有数字的方法回答了stackoverflow#35185中提出的问题，正如ltn100指出的那样。它使用O(1)的存储空间和O(n)的运行时间。如果暂时假设为32位整数，则XOR有7%的概率产生一个不同的数字。理由是：给定约4G个不同的数字进行XOR，和大约300M不在文件中的数字，每个位位置的设置位数有奇数或偶数的相等机会。因此，2^32个数字具有等同的可能性作为XOR结果，其中93%已经在文件中。请注意，如果文件中的数字并不都是不同的，则XOR方法的成功概率会提高。

- Ashley · Answer 9

从文件中删除所有空格和非数字字符，然后附加1。现在，您的文件包含一个未列在原始文件中的单个数字。

来自Carbonetc在Reddit上的帖子。

- Jonathan Amsterdam · Answer 10

出于某些原因，我看到这个问题就想到了对角化。我假设任意大的整数。

读取第一个数字，将其左侧填充零位直到有40亿个比特位。如果第一（高阶）比特位为0，则输出1；否则输出0。（你不需要实际进行左侧填充：如果数字中的比特位数不够，你只需输出1即可。）同样地，使用第二个数字并使用其第二个比特位。以此类推继续遍历文件。你将一次输出一个40亿比特位的数字，并且该数字与文件中的任何数字都不相同。证明：如果它与第n个数字相同，则它们将在第n个比特上达成一致，但是构造方式下它们并不一致。

生成一个不在已有 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万个比特位