查找数组中最常用的数字,内存有限

Question

如何在数组中找到最常用的数字？阵列可能非常大,例如2GB,我们只有有限的内存,比如100MB.

我正在考虑外部排序,即排序和复制彼此相邻的数字.或者hashma.但不知道如何处理有限的内存.我甚至不确定外部排序是否是一个好主意.

Answer 1

假设：

• 整数为 4 个字节。
• 2 GB 数组中的不同整数少于 (100 MB / 4 B) = (104857600 / 4) = 26214400 个。每个数字都映射到 0-26214399 索引范围。

我们来做直方图。

1. 在我们的 100 MB 空间中创建存储桶。它是一个名为 的整数数组histogram，最多可以存储 26214400 个计数器。计数器最初设置为 0。
2. 遍历 2 GB 数组一次。当你读的时候x，做histogram[x]++。
3. 找到 中的最大值histogram，迭代一次。如果最大值为histogram[i]，则i是出现次数最多的数字。

瓶颈是第 2 步，迭代 2 GB 数组，但我们只执行一次。

如果第二个假设不成立（即有超过 26214400 个不同的整数）：

为索引从 0 到 26214399 的数字制作直方图。保留直方图中出现频率最高的数字。为索引从 26214400 到 52428798 的数字制作直方图。保留直方图中最常见的数字和之前最常见的数字。等等。

在最坏的情况下，对于 2^32 个不同的数字，它将在该 2 GB 数组上执行 (2^32 / 26214400 + 1) = 164 次迭代。

一般来说，它将执行 (NUMBER_OF_DISTINCT_NUMBERS / 26214400 + 1) 次迭代。