记录梳理算法

我们得到这些包含16字节代码的~50GB数据文件,我想找到任何时间的1/2%或更多的代码.有什么方法可以一次性通过数据吗？

编辑:有大量代码 - 每个代码都可能不同.

EPILOGUE:我选择了Darius Bacon作为最佳答案,因为我认为最好的算法是对他所关联的多数元素的修改.大多数算法应该是可修改的,只能使用少量的内存 - 比如201代码,我认为会得到1/2%.基本上你只需要在流中计算最多201个不同的代码.一旦找到201个不同的代码,就会丢弃每个代码中的一个(从计数器中扣除1,忘记任何变为0的代码).最后,你最多下降了N/201次,因此任何出现次数超过的代码仍然存在.

但这是一个两遍算法,而不是一个.你需要第二次通过计算候选人的数量.实际上很容易看出,这个问题的任何解决方案都必须使用至少2次传递(你加载的第一批元素可能都不同,其中一个代码最终可能只有1/2%)

谢谢您的帮助!

Metwally等人,Efficient Computation of Frequent and Top-k Elements in Data Streams(2005).我在雅虎读到的一些其他相关论文是我现在找不到的; 但这看起来是一个好的开始.

编辑:啊,看看Brian Hayes这篇文章.由于Demaine等人的参考,它描绘了一个精确的算法.它只需很少的记忆即可完成,并产生一系列项目,包括您正在寻找的常用项目(如果存在的话).获得准确的计数需要(现在易处理的)第二遍.