问题是，给定一个包含40亿个整数的输入文件，提供一种算法来生成文件中不包含的整数，假设只有10 MB的内存。
搜索一些解决方案，其中之一是将整数存储到位向量块中(每个块代表40亿范围中的特定整数范围，块中的每个位代表一个整数(，并对每个块使用另一个计数器来计算每个块中的整数数。因此，如果整数的数量小于整数的块容量，请扫描块的位向量，找出哪些是丢失的整数。
我对这个解决方案的困惑是，有人提到，当块计数器阵列占用与位向量相同的内存时，最佳最小占地面积是。我很困惑，为什么在这种情况下，它是最佳的最小占地面积？
以下是我提到的计算细节，
Let N = 2^32.
counters (bytes): blocks * 4
bit vector (bytes): (N / blocks) / 8
blocks * 4 = (N / blocks) / 8
blocks^2 = N / 32
blocks = sqrt(N/2)/4
提前感谢，Lin
为什么它是最小的内存占用：
在您提出的解决方案中，有两个阶段：
-
计数每个块中的整数数量
这将使用
4*(#blocks)字节的内存。 -
使用位向量，每个位表示块中的一个整数。
这使用
(blocksize/8)字节的内存，即(N/blocks)/8。
如您所述，将2设置为相等会导致blocks = sqrt(N/32)中的结果。
这是最佳的，因为所需的内存是每个阶段所需内存的最大值(必须同时执行(。在第一阶段之后，除了在哪个块中搜索第二阶段之外，您可以忘记计数器。
优化
如果计数器在达到容量时饱和，那么每个计数器实际上不需要4个字节，而是需要3个字节。当计数器超过块中的整数数时，计数器达到容量。
在这种情况下，阶段1使用存储器的3*blocks，而阶段2使用(N/blocks)/8。因此，最佳为blocks = sqrt(N/24)。如果N为40亿，则块的数量约为12910，并且块大小为每个块309838个整数。这可容纳3个字节。
注意事项，以及具有良好平均案例性能的替代方案
您提出的算法只有在所有输入整数都不同的情况下才有效。如果整数不明显，我建议您简单地使用随机候选整数集方法。在随机候选整数集方法中，您可以随机选择1000个候选整数，并检查是否在输入文件中找不到任何整数。如果失败，可以尝试找到另一组随机的候选整数。虽然这在最坏情况下的性能较差，但在大多数输入的平均情况下，它会更快。例如，如果输入整数覆盖了99%的可能整数，那么平均而言，对于1000个候选整数，将找不到其中的10个。您可以伪随机选择候选整数，这样就不会重复候选整数，也可以保证在固定次数的尝试中，您将测试所有可能的整数。
如果每次都检查sqrt(N)候选整数，那么最坏情况下的性能可能与N*sqrt(N)一样好，因为您可能需要扫描所有N个整数sqrt(N)次。
如果您使用这种替代方案，您可以避免最坏的情况，如果它对第一组候选整数不起作用，则切换到您提出的解决方案。这可能会提供更好的平均情况性能(这是排序中的一种常见策略，首先使用快速排序，然后切换到堆排序，例如，如果出现最坏情况的输入(。
# assumes all integers are positive and fit into an int
# very slow, but definitely uses less than 10MB RAM
int generate_unique_integer(file input-file)
{
int largest=0
while (not eof(input-file))
{
i=read(integer)
if (i>largest) largest=i
}
return i++; #larger than the largest integer in the input file
}