713

我收到了这个面试问题:

给定一个具有 40 亿个整数的输入文件,提供一个算法来生成一个不包含在文件中的整数。假设您有 1 GB 内存。跟进如果您只有 10 MB 的内存,您会做什么。

我的分析:

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

我们可以进行外部排序,从而让我们知道整数的范围。

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

我的理解(阅读所有答案后):

假设我们谈论的是 32 位整数,则有 2 32 = 4*10 9 个不同的整数。

案例 1:我们有 1 GB = 1 * 10 9 * 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 6 * 8 位 = 8000 万位

解决方案:

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

  1. 通过文件的第一次遍历构建每个桶的计数器。
  2. 扫描桶,找到第一个命中少于 65536 的桶。
  3. 构建新的存储桶,其高 16 位前缀是我们在第 2 步到文件的第二遍中找到的
  4. 扫描step3构建的bucket,找到第一个没有命中的bucket。

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

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


对迟到的人的澄清:问题,正如所问的,并不是说文件中不包含确切的一个整数——至少大多数人不是这样解释的。不过,评论线程中的许多评论都是关于该任务的变体。不幸的是,将它引入评论线程的评论后来被其作者删除,所以现在看起来对它的孤立回复只是误解了一切。非常混乱,抱歉。

4

38 回答 38

539

假设“整数”表示 32 位:10 MB 的空间足以让您计算输入文件中有多少具有任何给定 16 位前缀的数字,一次通过所有可能的 16 位前缀输入文件。至少有一个桶被击中少于 2 16次。执行第二遍以查找该存储桶中哪些可能的数字已被使用。

如果它意味着超过 32 位,但仍然是有界的大小:按上述操作,忽略所有恰好落在(有符号或无符号;您的选择)32 位范围之外的输入数字。

如果“整数”表示数学整数:通读输入一次并跟踪您见过的最长数的最大数长度。完成后,输出最大值加 1一个多位数的随机数。(文件中的一个数字可能是一个需要超过 10 MB 才能准确表示的 bignum,但如果输入是一个文件,那么您至少可以表示适合其中的任何内容的长度)。

于 2011-08-22T21:28:00.790 回答
204

与确定性方法相比,统计信息算法使用更少的通道数解决了这个问题。

如果允许非常大的整数,则可以生成一个可能在 O(1) 时间内唯一的数字。像GUID这样的伪随机 128 位整数只会与集合中现有的 40 亿整数中的一个发生冲突,在每 640 亿个案例中不到一个。

如果整数被限制为 32 位,则可以使用远小于 10 MB 的空间生成一个可能在单次传递中唯一的数字。伪随机 32 位整数与 40 亿个现有整数之一发生冲突的几率约为 93% (4e9 / 2^32)。1000 个伪随机整数全部碰撞的几率小于 120000 亿分之一(碰撞几率 ^ 1000)。因此,如果一个程序维护一个包含 1000 个伪随机候选的数据结构并遍历已知整数,从候选中消除匹配项,那么几乎可以肯定会找到至少一个不在文件中的整数。

于 2011-08-23T05:04:52.000 回答
147

关于这个问题的详细讨论已在Jon Bentley “Column 1. Cracking the Oyster” Programming Pearls Addison-Wesley pp.3-10 中讨论过

Bentley 讨论了几种方法,包括外部排序、使用多个外部文件的合并排序等,但 Bentley 建议的最佳方法是使用位域的单通道算法,他幽默地将其称为“Wonder Sort”:) 解决问题,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 的算法对文件进行一次遍历,查找set数组中的适当位,然后使用test上面的宏检查这个数组以找到丢失的数字。

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

HTH。

于 2011-08-23T04:20:53.810 回答
124

由于问题没有指定我们必须找到不在文件中的最小可能数字,我们可以生成一个比输入文件本身长的数字。:)

于 2011-08-23T11:07:04.213 回答
60

对于 1 GB RAM 变体,您可以使用位向量。您需要分配 40 亿位 == 500 MB 字节数组。对于从输入中读取的每个数字,将相应的位设置为“1”。完成后,遍历这些位,找到第一个仍然为“0”的位。它的指数就是答案。

于 2011-08-22T21:17:57.937 回答
49

如果它们是 32 位整数(可能来自接近 2 32的约 40 亿个数字的选择),那么您的 40 亿个数字列表将最多占可能整数的 93%(4 * 10 9 / (2 32 ) )。因此,如果您创建一个 2 32位的位数组,每个位初始化为零(这将占用 2 29字节 ~ 500 MB 的 RAM;请记住一个字节 = 2 3位 = 8 位),请通读您的整数列表并对于每个 int 将相应的位数组元素从 0 设置为 1;然后读取您的位数组并返回仍然为 0 的第一位。

如果您的 RAM (~10 MB) 较少,则需要稍微修改此解决方案。10 MB ~ 83886080 位仍然足以为 0 到 83886079 之间的所有数字做一个位数组。所以你可以阅读你的整数列表;并且只记录位数组中 0 到 83886079 之间的#s。如果数字是随机分布的;以压倒性的概率(大约10 -2592069相差 100% )你会发现一个缺失的 int)。事实上,如果您只选择 1 到 2048 之间的数字(只有 256 字节的 RAM),您仍然会发现丢失的数字占绝大多数(99.9999999999999999999999999999999999999999999999999999999999999995%)。

但是,假设没有大约 40 亿个数字;你有类似 2 32 - 1 个数字和少于 10 MB 的 RAM;所以任何小范围的整数只有很小的可能性不包含数字。

如果您保证列表中的每个 int 都是唯一的,您可以将数字相加,然后减去一个 # 缺失的总和 (½) (2 32 ) (2 32 - 1) = 9223372034707292160 以找到缺失的 int . 但是,如果 int 出现两次,则此方法将失败。

但是,您总是可以分而治之。一种简单的方法是通读数组并计算前半部分(0 到 2 31 -1)和后半部分(2 31 , 2 32)中的数字数量。然后选择数字较少的范围并重复将该范围分成两半。(假设 (2 31 , 2 32 ) 中的数字少了两个,那么您的下一个搜索将计算 (2 31 , 3*2 30 -1), (3*2 30 , 2 32 ) 范围内的数字。保持重复直到你找到一个零数字的范围并且你有你的答案。应该用 O(lg N) ~ 32 读取数组。

这种方法效率低下。我们在每个步骤中只使用两个整数(或大约 8 字节的 RAM 和一个 4 字节(32 位)整数)。更好的方法是分成 sqrt(2 32 ) = 2 16 = 65536 个 bin,每个 bin 中有 65536 个数字。每个 bin 需要 4 个字节来存储其计数,因此您需要 2个 18字节 = 256 kB。所以 bin 0 是 (0 to 65535=2 16 -1), bin 1 是 (2 16 =65536 to 2*2 16 -1=131071), bin 2 是 (2*2 16 =131072 to 3*2 16 - 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 亿个整数列表;并计算 2 16 个bin中的每个 bin 中有多少个整数,并找到一个不完整的 bin,它不包含所有 65536 个数字。然后你再次通读 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
于 2011-08-23T05:58:06.850 回答
39

为什么搞得这么复杂?您要求文件中不存在的整数?

根据指定的规则,您唯一需要存储的是文件中迄今为止遇到的最大整数。读取整个文件后,返回大于该值的数字 1。

没有命中 maxint 或任何东西的风险,因为根据规则,对整数的大小或算法返回的数字没有限制。

于 2011-08-23T14:38:13.593 回答
34

这可以使用二进制搜索的变体在非常小的空间内解决。

  1. 从允许的数字范围开始,04294967295

  2. 计算中点。

  3. 循环遍历文件,计算有多少数字等于、小于或大于中点值。

  4. 如果没有数字相等,你就完成了。中点数就是答案。

  5. 否则,请选择数字最少的范围,然后使用此新范围从步骤 2 开始重复。

这将需要对文件进行多达 32 次线性扫描,但它只会使用几个字节的内存来存储范围和计数。

这与Henning 的解决方案基本相同,只是它使用两个 bin 而不是 16k。

于 2011-08-23T20:17:28.297 回答
27

编辑好的,这并没有完全考虑清楚,因为它假设文件中的整数遵循一些静态分布。显然他们不需要,但即便如此,人们也应该试试这个:


大约有 43 亿个 32 位整数。我们不知道它们在文件中是如何分布的,但最坏的情况是香农熵最高的情况:均匀分布。在这种情况下,文件中不出现任何一个整数的概率为

( (2³²-1)/2³² )⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

香农熵越低,平均这个概率就越高,但即使在最坏的情况下,我们有 90% 的机会在用随机整数猜测 5 次后找到一个未出现的数字。只需使用伪随机生成器创建此类数字,并将它们存储在列表中。然后在 int 之后阅读 int 并将其与您的所有猜测进行比较。当有匹配项时,删除此列表条目。在浏览完所有文件后,您可能会有不止一个猜测。使用其中任何一个。在没有猜测剩余的罕见(即使在最坏的情况下也有 10%)事件中,获得一组新的随机整数,这次可能更多(10->99%)。

内存消耗:几十个字节,复杂度:O(n),开销:nelectable 因为大部分时间将花在不可避免的硬盘访问上,而不是比较整数。


当我们假设静态分布时,实际最坏的情况是每个整数都出现最大值。一次,因为只有 1 - 4000000000/2³² ≈ 6% 的整数不会出现在文件中。所以你需要更多的猜测,但这仍然不会消耗大量的内存。

于 2011-08-23T01:49:48.037 回答
24

如果 [0, 2^ x - 1] 范围内缺少一个整数,则只需将它们全部异或。例如:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(我知道这并不能完全回答这个问题,但它是对一个非常相似的问题的一个很好的回答。)

于 2011-08-24T02:43:07.583 回答
20

他们可能想看看你是否听说过概率布隆过滤器,它可以非常有效地确定一个值是否不是大集合的一部分,(但只能以高概率确定它是集合的成员。)

于 2011-08-23T21:20:45.163 回答
17

根据原始问题中的当前措辞,最简单的解决方案是:

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

于 2011-08-23T03:04:09.283 回答
14

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

于 2011-08-22T21:17:04.887 回答
12

如果没有大小限制,最快的方法是取文件的长度,生成文件的长度+1个随机数字(或者只是"11111..." s)。优点:您甚至不需要读取文件,并且可以将内存使用量减少到几乎为零。缺点:您将打印数十亿位数字。

但是,如果唯一的因素是最大限度地减少内存使用,而没有其他重要的因素,这将是最佳解决方案。它甚至可能让你获得“最严重的规则滥用”奖。

于 2011-08-24T06:09:23.017 回答
11

如果我们假设数字的范围总是 2^n(2 的偶数次幂),那么异或将起作用(如另一张海报所示)。至于为什么,让我们证明一下:

理论

给定任何基于 0 的整数范围,2^n其中包含缺少一个元素的元素,您可以通过简单地将已知值异或在一起以产生缺失的数字来找到缺失的元素。

证据

让我们看看 n = 2。对于 n=2,我们可以表示 4 个唯一整数:0、1、2、3。它们的位模式为:

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

现在,如果我们看一下,每个位都被设置了两次。因此,由于它被设置了偶数次,并且数字的异或将产生 0。如果缺少单个数字,异或将产生一个数字,当与缺少的数字异或时将导致0. 因此,缺失的数和得到的异或数完全相同。如果我们删除 2,结果 xor 将是10(或 2)。

现在,让我们看一下n+1。我们称每个位被设置的次数为nx每个位被设置的次数为n+1 y。的值y将等于,y = x * 2因为存在位设置为 0 的x元素和位设置为 1 的元素。并且由于将始终为偶数,因此每个位将始终设置偶数次。n+1xn+12xn+1

因此,由于n=2有效,并且n+1有效,xor 方法将适用于 的所有值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。但它确实需要 2 次通过通过文件(第一个获取最小值,第二个计算丢失的 int)。

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 的幂。这仅在缺少一个位时才有效。它需要 2 遍未排序的文件,但每次都会找到单个丢失的数字:

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 左右。然后,它在计算异或时计算要附加的未排序值的数量。然后,它将未排序值的计数加 1 以处理缺失值(计算缺失值)。然后,继续对 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;
于 2011-08-24T13:56:57.070 回答
9

诡计问题,除非引用不正确。只需通读一次文件以获得最大整数n,然后返回n+1

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

于 2011-08-22T21:37:48.217 回答
9

检查输入文件的大小,然后输出任何太大而无法由该大小的文件表示的数字。这似乎是一个廉价的技巧,但它是面试问题的创造性解决方案,它巧妙地回避了记忆问题,而且它在技术上是 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 bitcount -1,它总是大于2 bitcount。从技术上讲,您必须击败的数字是2 bitcount - (4 * 10 9 - 1),因为您知道文件中有 (40 亿 - 1) 个其他整数,即使经过完美压缩,它们至少会占用各一位。

于 2011-08-24T04:16:11.087 回答
8
  • 最简单的方法是找到文件中的最小数字,并返回小于该数字的 1。对于 n 个数字的文件,这使用 O(1) 存储和 O(n) 时间。但是,如果数字范围有限,它将失败,这可能会使 min-1 不是数字。

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

  • 还提到了具有 2^16 个计数桶的 2-pass 方法。它读取 2*n 个整数,因此使用 O(n) 时间和 O(1) 存储,但它无法处理超过 2^16 个数字的数据集。但是,通过运行 4 次而不是 2 次,它很容易扩展到(例如)2^60 个 64 位整数,并且通过仅使用尽可能多的 bin 并相应地增加通过次数来轻松适应使用微型内存,在这种情况下运行时间不再是 O(n),而是 O(n*log n)。

  • 正如 ltn100 所指出的,到目前为止,rfrankel 和 ircmaxell 提到的将所有数字异或的方法回答了stackoverflow#35185中提出的问题。它使用 O(1) 存储和 O(n) 运行时间。如果目前我们假设 32 位整数,XOR 有 7% 的概率产生一个不同的数字。基本原理:给定〜4G不同的数字一起异或,并且大约。300M 不在文件中,每个位位置的设置位数有相等的奇数或偶数机会。因此,2^32 个数字与 XOR 结果出现的可能性相同,其中 93% 已经在文件中。请注意,如果文件中的数字并非全部不同,则 XOR 方法的成功概率会上升。

于 2011-08-22T21:35:45.193 回答
7

出于某种原因,一读到这个问题,我就想到了对角化。我假设任意大的整数。

读第一个数字。用零位填充它,直到你有 40 亿位。如果第一个(高位)位为 0,则输出 1;否则输出 0。(您实际上不必左填充:如果数字中没有足够的位,您只需输出 1。)对第二个数字执行相同操作,除了使用它的第二个位。以这种方式继续浏览文件。您将一次输出一个 40 亿位的数字,并且该数字与文件中的任何数字都不相同。证明:与第n个数相同,那么他们会在第n位上达成一致,但他们不通过构造。

于 2011-08-24T14:49:07.700 回答
6

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

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

假设每个整数都是 32 位的,如果完成位标记,它们将很方便地放入 1 GB 的 RAM。

于 2011-08-22T21:18:40.503 回答
6

只是为了完整起见,这是另一个非常简单的解决方案,它很可能需要很长时间才能运行,但使用的内存很少。

让所有可能的整数是从int_min到的范围int_maxbool isNotInFile(integer)如果文件不包含某个整数,则返回 true,否则返回 false(通过将该特定整数与文件中的每个整数进行比较)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}
于 2011-08-24T11:51:36.027 回答
6

从文件中去除空格和非数字字符并附加 1。您的文件现在包含原始文件中未列出的单个数字。

来自 Carbonetc 的 Reddit。

于 2011-08-24T12:39:39.137 回答
5

对于 10 MB 内存限制:

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

完成后,只需走一条之前没有创建过的路径来创建请求的号码。

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

编辑

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

编辑二

也不需要完全构建树。如果数字相似,您只需要构建深层分支。如果我们也剪树枝,那么这个解决方案实际上可能会奏效。

于 2011-08-22T21:38:36.217 回答
5

我将回答 1 GB 版本:

问题中没有足够的信息,所以我先陈述一些假设:

整数为 32 位,范围为 -2,147,483,648 到 2,147,483,647。

伪代码:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}
于 2011-08-23T12:39:39.033 回答
4

只要我们在做创造性的答案,这里就是另一个。

使用外部排序程序对输入文件进行数字排序。这适用于您可能拥有的任何内存量(如果需要,它将使用文件存储)。通读排序的文件并输出丢失的第一个数字。

于 2013-07-12T19:38:35.707 回答
3

正如瑞安所说的那样,对文件进行排序,然后遍历整数,当一个值被跳过时,你就有了:)

在downvoters 处编辑:OP 提到可以对文件进行排序,因此这是一种有效的方法。

于 2011-08-22T21:15:30.120 回答
3

位消除

一种方法是消除位,但这实际上可能不会产生结果(可能不会)。伪代码:

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 };

遍历文件中的每个值并尝试将其从当前范围中删除。这种方法没有内存保证,但它应该做得很好。

于 2011-08-23T12:26:37.180 回答
3

2 128*10 18 + 1 (即 (2 8 ) 16*10 18 + 1 ) - 它不能成为今天的通用答案吗?这代表了一个不能保存在 16 EB 文件中的数字,这是任何当前文件系统中的最大文件大小。

于 2011-08-24T09:57:39.213 回答
3

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

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

从零开始运行总计,并为文件中的每个整数添加具有 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";
  }
}
于 2011-08-24T10:37:54.280 回答
2

如果您不假设 32 位约束,只需返回一个随机生成的 64 位数字(如果您是悲观主义者,则返回 128 位)。碰撞的几率是1 in 2^64/(4*10^9) = 4611686018.4(大约 40 亿分之一)。大多数时候你是对的!

(开玩笑……有点。)

于 2011-08-24T08:12:50.080 回答
2

给定一个具有 40 亿个整数的输入文件,提供一个算法来生成一个不包含在文件中的整数。假设您有 1 GiB 内存。如果您只有 10 MiB 的内存,请跟进您会做什么。

文件大小为 4 * 109 * 4 字节 = 16 GiB

如果是 32 位无符号整数

0 <= Number < 2^32
0 <= Number < 4,294,967,296

我提出的解决方案:没有错误检查的 C++

#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

int main ()
{
    const long SIZE = 1L << 32;

    std::vector<bool> checker(SIZE, false);

    std::ifstream infile("file.txt");  // TODO: error checking

    unsigned int num = 0;

    while (infile >> num)
    {
        checker[num] = true ;
    }

    infile.close();

    // print missing numbers

    for (long i = 0; i < SIZE; i++)
    {
        if (!checker[i])
            cout << i << endl ;
    }

    return 0;
}

复杂

  • 空间 ~ 2 32位 = 2 29字节 = 2 19 KB = 2 9 MB = 1/2 GB
  • 时间~单程
  • 完整性~是的
于 2015-05-14T10:06:06.223 回答
1

也许我完全错过了这个问题的重点,但是您想从已排序的整数文件中找到一个缺少的整数?

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

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

这个问题的解决方案似乎微不足道。

于 2011-08-24T00:28:31.447 回答
1

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

第一步就像快速排序的第一步。选择一个整数 x,并使用它遍历数组,将所有小于 x 的值放在其左侧,将大于 x 的值放在其右侧。找出 x 的哪一侧有最多的可用槽(整数不在列表中)。这很容易通过将 x 的值与其位置进行比较来计算。然后在 x 的那一侧的子列表上重复分区。然后重复子列表上可用整数数量最多的分区,等等。比较总次数到一个空范围应该是大约 40 亿,给或取。

于 2011-08-25T05:52:51.487 回答
1

通过将未访问的整数范围存储在某些树结构中,您可以在读取现有整数后加快查找缺失整数的速度。

您将从存储 [0..4294967295] 开始,每次读取一个整数时,您都会拼接它所在的范围,当它为空时删除一个范围。最后,您将获得范围中缺少的确切整数集。因此,如果您将 5 视为第一个整数,您将拥有 [0..4] 和 [6..4294967295]。

这比标记位要慢很多,因此它仅适用于 10MB 的情况,前提是您可以将树的较低级别存储在文件中。

存储这种树的一种方法是将范围的开始作为键,将范围的结束作为值的 B 树。最坏的情况是当你得到所有奇数或偶数整数时,这意味着为树存储 2^31 个值或数十 GB ......哎呀。最好的情况是一个排序的文件,你只对整个树使用几个整数。

所以不是真正的正确答案,但我想我会提到这种方式。我想我会通过面试;-)

于 2011-09-28T21:43:13.273 回答
0

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

于 2011-08-24T02:45:10.063 回答
0

我想出了以下算法。

我的想法:遍历所有整数文件一次,并为每个位位置计算它的 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 是正确的方法

于 2012-02-06T22:12:25.557 回答
0

老问题,但我想知道“非功能性”要求。在我看来,应该给出一个线索——如果这个问题是在其他地方提出的,而不是在一本书中,然后继续讨论所有的可能性和利弊。很多时候,这似乎是求职面试中的问题,让我感到困惑,因为在不知道软要求的情况下无法给出明确的答案,即“查找丢失的数字必须非常快,因为它在一秒钟内使用了 x 次”。

我认为这样的问题或许可以给出一个合理的答案。

  • 我会将所有数字合并排序到一个新文件中,每个整数使用 4 个字节。当然,一开始这样做会很慢。但它可以用少量的内存来完成(你不需要把所有的东西都保存在 RAM 中)
  • 使用二进制搜索来检查数字是否存在于预排序的文件中。因为我们每个值保留 4 字节,所以这没问题

缺点:

  • 文件大小
  • 慢速第一排序 - 但只需要一次

好处:

  • 查找速度非常快

再说一次,对于一本书来说,这是一个非常好的问题。但我认为,当要解决的问题不完全清楚时,当寻求单一的最佳解决方案时,这是一个奇怪的问题。

于 2013-10-06T11:49:18.340 回答
-1

当然,并且以有限的经验说话(刚开始在 Uni 学习 java),您可以通过一组(桶)int 运行,如果找不到数字,请处理桶。这既可以释放空间,又可以对每个数据单元进行检查。如果找到您要查找的内容,请将其添加到计数变量中。会花费很长时间,但是,如果您为每个部分创建多个变量并通过每个变量运行检查计数并确保它们同时退出/处理,变量存储不应该增加?并将加快检查过程。只是一个想法。

于 2014-12-15T14:28:19.150 回答