algorithm - 一个包含 100 万个整数的大文件，找到最常出现的整数的最快方法是什么？

Question

基本方法是使用数组或 HashMap 创建数字直方图并选择最频繁出现的数字。

在这种情况下，我们假设无法将文件中的所有数字都加载到主内存中。

我能想到的一种方法是使用外部合并/快速排序进行排序，然后逐 block 计算频率。由于它们已排序，因此我们不必担心在带有数字的序列完成后再次出现该数字。

是否有更好、更有效的方法来做到这一点？

Answer 1

好吧，一百万不再那么多了，所以让我们假设我们谈论的是几十亿整数。

在这种情况下，我建议您对它们进行散列处理，并使用顶部 N 将它们分成 2^N 个存储桶(单独的文件或同一文件的预分配部分) > 他们的散列值的位。

您会选择 N，这样生成的桶很可能小到足以在内存中处理。

然后，您将通过计算哈希表或类似表中每个唯一值的出现次数来处理每个存储桶。

万一桶中的唯一值太多而无法放入 RAM，请使用哈希的下一个 N 位重新分区并重试。