使用10 MB内存为40亿个整数(关于找到优化的块大小)

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

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

在您提出的解决方案中,有两个阶段:

1. 计算每个块中的整数数

   这使用4*(#blocks)内存字节.

2. 使用位向量表示块中的整数.

   这使用(blocksize/8)了内存字节,即(N/blocks)/8.

blocks = sqrt(N/32)如上所述,将2设置为相等.

这是最佳的,因为所需的内存是每个阶段所需内存的最大值(必须同时执行).在第一阶段之后,您可以忘记计数器,除了要搜索第2阶段的块.

优化

如果计数器在达到容量时饱和,那么每个计数器实际上不需要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)次.

如果使用此替代方法,则可以避免最坏情况时间,如果它不适用于第一组候选整数,则切换到建议的解决方案.这可能会提供更好的平均案例性能(这是排序中首先使用快速排序的常用策略,然后在切换到heapsort之前,例如,如果看起来存在最坏情况输入).