查找数组中最频繁的数字，内存有限

如何查找数组中最频繁的数字？该阵列可能非常大，例如2GB，我们只有有限的内存，比如100MB。查找数组中最频繁的数字，内存有限

我在考虑外部排序，这是排序和不是复制是彼此相邻号码。或者hashma。但不知道如何处理有限的记忆。我甚至不确定外部排序是否是一个好主意。

来源

2014-01-17 JudyJiang

可以代替排序，然后遍历数组超过想到的。但是它会破坏你的原始数组。 –

@JudyJiang是否有该数字所在的范围？ –

也看看我的答案在这里（http://stackoverflow.com/a/23441932/191148） –

假设：

整数为4个字节。
有小于（100 MB/4 B）=（4分之104857600）= 2 GB的阵列中的26214400个不同的整数。每个数字映射到0-26214399指数范围。

让我们做柱状图。

制作水桶在我们的100 MB的空间。这是一个称为histogram的整数数组，它可以存储多达26214400个计数器。计数器初始化设置为0.
通过2 GB数组迭代一次。当您阅读x时，请执行histogram[x]++。
查找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）次迭代。

来源

2014-01-17 18:00:37

@Downvoter你能评论（所以也许我可以改善我的答案）？ –

您的第一个建议是假设您确切知道存在哪些数字 - 否则即使只有极少数不同的数字，也可能无法将出现的数字双注射到0-26214399范围内。你的第二个建议效率很低（例如，考虑到op实际上有64位数的情况......） – example

如果你的内存有限，但处理能力合理数量和超快的速度不是问题，根据您的数据集，你可以尝试像：

通过迭代计算阵列数字1的数1000.保持最大的数量。然后计算1001到2000.保持这些之间的最大数量，并从第一批最大的一个。重复，直到所有数字都被计算在内。

我敢肯定有如此多的优化根据您的数据集的细节。

来源

2014-01-17 17:59:12 Matt

这是行不通的。具有最高计数的单个数字很可能在不具有最高计数的范围内。例如，如果你的号码的范围是0-100，你将它们分为桶10.说数字21出现3次，这是在0-20范围内的唯一号码。但是每个从10到19的数字都会出现一次。你会选择10的桶，扔掉20桶。 –

我想你误会了。你计算每个数字从1到10.说5出现3次，所以你保持5 = 3。然后你计算从11到20的每个数字，17出现2次。你保持了最高的运行最高（5 = 3）和最新最高（17 = 2），所以你保持5 = 3。那有意义吗？ – Matt

我误解了你的方法。你所描述的将会起作用。我试图解决我的失望，但它是说，答案必须先编辑。 –

在最糟糕的情况下，除了一次出现两次的数字之外，所有的数字都是不同的，除非您有两个重复的数字同时加载到主存储器中，否则无法在主存中检测到该数字，如果您的总数据量远远大于主内存大小，那么这种情况不会发生。在这种情况下，最好的做法是批量排序数字并将其保存到文件中的磁盘，然后执行合并排序合并步骤，将所有已排序的文件一次一页一页读入内存，然后输出合并后的排序列表到一个新的文件。然后按顺序浏览聚合排序文件，并计算您看到每个数字的次数，并记录最多次发生的次数。

如果您认为最常见的数字是50％或更高的频率，那么您可以做得更好。你可以用一次一次的数字列表来解决这个问题。基本上，您首先将最常用的值（MCV）初始化为第一个数字，然后将计数器N初始化为1，然后查看列表。如果列表中的下一个数字是MCV，则将N加1。否则，将N减1。如果N为0，并且下一个数字与MCV不同，则将MCV设置为新数字并将N设置为1.很容易证明这将以存储在MCV中的最常见值。

来源

2014-01-17 19:19:23 user2566092

假设4字节整数，可以将（100/4）= 25MB整数放入可用内存。

通读您的大文件，计算0到25MB-1范围内的每个出现次数和次数。使用大数组来累计计数。
找到最频繁发生的号码，存储号码及其频率并清除阵列。
通读大文件，重复计数过程中的数字范围25MB ... 50MB-1。
查找新数组中最常出现的数字。将它与步骤2中存储的数字/频率进行比较。存储频率较高的数字/频率并清除数组。
泡沫，冲洗，重复。

ETA：如果我们可以设想有一个单一的答案，那没有两个具有相同频率最高的不同的号码，那么你就可以放弃所有的数字，如果一个特定范围内的阵列显示平局。否则，存储每个范围的赢家的问题变得更加复杂。

来源

2014-01-18 11:20:55 rossum

根据的假设是什么，这样做可能会使用MJRTY算法的更好的方法：

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

及其推广：

http://www.cs.yale.edu/homes/el327/datamining2011aFiles/ASimpleAlgorithmForFindingFrequentElementsInStreamsAndBags.pdf

的想法是只要有两个变量（一个计数器和一个值存储器），就可以确定，如果存在多数元素（严格出现超过50％的时间），那么该元素是什么。泛化要求（k + 1）个计数器和值存储器来查找出现100/k％的元素。因为这些只是大多数人的候选人（如果存在k个多数元素，那就是他们;但是如果没有k个多数元素，那么这些只不过是偶然的随机元素），第二次传递这些数据可以帮助您确定候选人的确切数量，并确定哪一个（如果有的话）是多数元素。

这是非常快速和高效的内存。

很少有其他的优化，但随着内存4KB，你应该能够找到好的概率数据的2GB的大部分元素 - 这取决于你的数据类型。

来源

2014-05-10 09:12:43

查找数组中最频繁的数字，内存有限

回答

相关问题