0

我正在阅读有关从 40 亿个 32 位整数系列中查找缺失数字的问题Programming Pearls，但无法完全找到解决方案。

给定一个包含最多 40 亿个随机顺序的 32 位整数的顺序文件，找到一个不在文件中的 32 位整数。
约束：几百字节的主内存，但在磁盘上大量使用外部临时文件

所描述的解决方案是一个过程，我们使用高位分隔范围内的数字（即在第一遍中，我们将具有前导0位的那些写入一个文件，将具有前导位的那些写入另一个文件1。我们继续使用第二个位等。 ) 并将包含小于该范围内一半数字的一半用作新搜索范围。

我用谷歌搜索并在SO中找到了一个类似的帖子，它并没有完全回答我的问题，即如何找到确切的数字（我不明白二进制搜索如何适合单独的范围）。
@Damien_The_Unbeliever 的答案似乎是最相关的，但从我的角度来看，我认为按照这个过程我们最终会得到 2 个文件：一个范围内有 2 个数字的文件和一个有 1 个数字的文件。
通过将一个文件中的（一个）数字与其他文件中最大的数字相减，我们可以得到一个缺失的数字（不需要位掩码，我不太确定我们是否真的可以应用位掩码，因为范围在任何时候都是未知的）。

我错了吗？有人可以帮助解决这个问题吗？

4

3 回答 3

3

您无需复制数据本身或将任何内容写入磁盘；只需计算数据的某些分区的成员即可识别开口。在传递次数和内存之间进行权衡（更多的内存允许更多的计数，更小的分区）。

这是8遍的解决方案。我们将一次使用 4 位对数据进行分区。2^4 = 16 个可能的值，因此我们需要 64 个字节来存储 16 个分区中的每个分区的计数。所以每个 4 位半字节值都有一个相关的计数。

通过数据，增加与数字前四位中的半字节匹配的相关计数。如果分区已满，则其计数将为 2^28。选择一个未满的半字节——这将是你结果的第一个半字节。

将您的计数归零并再次通过，忽略与第一个半字节不匹配的数字并增加与该数字中的第二个半字节相关的计数。一个完整的第二个半字节将具有 2^24 的值。挑一个没满的。

以这种方式进行，直到你有所有 8 个半字节，并且在 O(N) 中有你的答案。

如果您一次只检查一位，这将是一个需要 32 遍的二进制搜索。（编辑：不是真正的二分搜索，因为您仍然需要读取您正在跳过的值。这就是为什么它是 O(N)。请参阅下面的编辑。）如果您有 KB 的内存用于计数，您可以这样做4次通过；使用 256 KB，您可以在 2 内完成 --- 实际上是 128 KB，因为您可以使用短整数进行计数。在这里，我们被限制在几百个字节 --- 可能是 6 位/6 次传递/256 字节？

编辑： Li-aung Yip 的解决方案可以更好地扩展，显然它可以修改为一次通过不止一位进行分区。如果写入比读取慢，那么最好的解决方案可能是这个只读答案和 Li-aung Yip 基于磁盘的答案之间的混合。

如上所述计算半字节，然后在计算第二组半字节时，根据第二半字节仅将匹配第一个半字节的数字（或可能只是它们的最后 28 位）写入 16 个文件。

选择第二个半字节并读取它以获取第三个半字节的计数，仅写入与第二个半字节匹配的数字，等等。如果文件接近容量，如果数字分布相当均匀，或者如果你选择最少满每次半字节，您必须写入不超过文件大小的 6.66% (1/16+1/16^2...)。

于 2012-04-14T23:07:57.030 回答
2

在将数字重复二进制分区为越来越小的文件后，您将得到：

  • 一堆包含两个数字的文件，它们仅在最后一个有效位上有所不同
  • 一个文件，其中只有一个数字。

通过翻转文件中数字的最后一位来获取丢失的数字。

以从 0x00 到 0x07 的数字为例，缺少 0x04：

000
001

010
011

... (missing)
101

110
111

取101，翻转最低有效位，然后得到100，这是缺少的0x04。

于 2012-04-14T10:07:25.647 回答
1

使用 32 位整数可以表示 40 亿个整数。将数字与自身进行 XOR 是在汇编代码中将寄存器归零的标准技巧。如果您保证只有一个数字丢失，那么整数的按位异或就可以解决问题，这是一种 O(N) 解决方案，只需要一个额外的 32 位整数空间。考虑一个简单的例子，一个 3 位数字，因此数字 0-7 可表示，其中一个缺失。假设 6 (110) 缺失 缺失 = n1 XOR n2 XOR n3 XOR .. XOR n7。= 000 异或 001 异或 010 异或 011 异或 100 异或 101 异或 111

如果问题是找到 1 到 100 之间的缺失数字，您需要开始我对必须排除的元素进行异或运算。通过屏蔽数字中的位，可以使用 AND 从 32 位整数范围下降到更小的范围。

于 2012-05-31T00:02:13.030 回答