arrays - 在内存有限的情况下找到数组中出现次数最多的数字

Question

如何找到数组中出现频率最高的数？该数组可以非常大，例如 2GB，而我们只有有限的内存，比如 100MB。

我正在考虑外部排序，即排序而不是复制彼此相邻的数字。或大麻。但是不知道如何处理有限的内存。我什至不确定外部排序是否是个好主意。

Answer 1

在最坏的情况下，除了一个数字出现两次之外，所有数字都是不同的，并且无法在主内存中检测到这一点，除非您将两个重复的数字同时加载到主内存中，这是不太可能的如果您的总数据大小远大于主内存大小，则不进行排序。在那种情况下，aysmptotically 最好的办法是分批对数字进行排序并保存到文件中的磁盘，然后执行合并排序合并步骤将所有排序的文件一次几行读入内存，并输出合并排序列表到一个新文件。然后你按顺序浏览聚合排序文件并计算你看到每个数字的次数，跟踪哪个数字出现次数最多。

如果您假设最频繁出现的数字是 50% 或更高频率，那么您可以做得更好。您只需遍历一次数字列表就可以通过不断增加的内存来解决问题。基本上，您首先将最常见的值 (MCV) 初始化为第一个数字，并将计数器 N 初始化为 1。然后遍历列表。如果列表中的下一个数字是 MCV，则将 N 加一。否则将 N 减 1。如果 N 为 0 且下一个数字与 MCV 不同，则将 MCV 设置为新数字并将 N 设置为 1。很容易证明这将以存储在 MCV 中的最常见值终止.