对 40 亿个整数使用 10 MB 的内存（关于找到优化的块大小）

Question

问题是，给定一个包含 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

提前致谢，林

Answer 1

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

Answer 2

为什么它是最小的内存占用：

在您提出的解决方案中，有两个阶段：

计算每个块中的整数个数

这使用 4*(#blocks) 字节内存。
使用位向量，每个位代表块中的一个整数。

这使用 (blocksize/8) 字节的内存，即 (N/blocks)/8。

如您所述，将 2 设置为相等会导致 blocks = sqrt(N/32)。

这是最优的，因为所需内存是每个阶段所需内存的最大值（必须同时执行）。第一阶段之后，你可以忘记计数器，除了在哪个块中搜索阶段 2。

优化

如果您的计数器在达到容量时饱和，您实际上不需要每个计数器 4 个字节，而是 3 个字节。当计数器超过块中整数的数量时，计数器达到容量。

在这种情况下，阶段 1 使用 3*blocks 内存，阶段 2 使用 (N/blocks)/8。因此，最优的是blocks = sqrt(N/24)。如果 N 为 40 亿，则块数约为 12910，块大小为每个块 309838 个整数。这适合 3 个字节。

注意事项，以及具有良好平均案例性能的备选方案

你提出的算法只有在所有输入整数都不同的情况下才有效。如果整数不明显，我建议您简单地使用随机候选整数集方法。在随机候选整数集方法中，您可以 select 随机说出 1000 个候选整数，然后检查是否在输入文件中找不到任何候选整数。如果你失败了，你可以尝试找到另一组随机的候选整数。虽然这在最坏情况下的性能很差，但在大多数输入的平均情况下它会更快。例如，如果输入整数覆盖了 99% 的可能整数，那么平均而言，有 1000 个候选整数，其中 10 个将找不到。您可以 select 伪随机候选整数，这样您就不会重复候选整数，并且还可以保证在固定次数的尝试中，您将测试所有可能的整数。

如果每次检查 sqrt(N) 个候选整数，那么最坏情况下的性能可能与 N*sqrt(N) 一样好，因为您可能必须扫描所有 N 个整数 sqrt(N) 次.

如果您使用此替代方案，则可以避免出现最坏情况的时间，如果它不适用于第一组候选整数，则切换到您提出的解决方案。这可能会提供更好的平均情况性能（这是一种常见的排序策略，首先使用快速排序，然后再切换到堆排序，例如，如果出现最坏情况输入）。

对 40 亿个整数使用 10 MB 的内存（关于找到优化的块大小）

using 10 MB of memory for four billion integers (about finding the optimized block size)

algorithm

bit-manipulation

bit

为什么它是最小的内存占用：

优化

注意事项，以及具有良好平均案例性能的备选方案