日志合并算法

Question

日志合并算法

14

我们得到了一些大小约为50GB的数据文件，其中包含16字节代码，我想找到任何发生1/2%或更多次的代码。有没有办法在对数据进行单个遍历时做到这一点？

编辑：有大量的代码-每个代码都可能不同。

结语：我选择了Darius Bacon作为最佳答案，因为我认为最好的算法是他链接的majority element的修改版。主要算法应该可以修改为仅使用极少量的内存-例如201个代码以获取1/2%。基本上，您只需要遍历数据并计数至201个不同的代码。一旦您找到201个不同的代码，您就会删除每个代码中的一个（从计数器中减去1，忘记任何变为0的计数器）。最后，您最多会删除N / 201次，因此任何出现次数超过该值的代码必须仍然存在。

但这是一个两遍算法，而不是一个。您需要第二次遍历来统计候选人的计数。实际上很容易看出，解决此问题的任何解决方案都必须至少使用2遍（您加载的第一批元素都可能不同，其中一个代码可能最终正好为1/2％）。

感谢您的帮助！

- Gwildore

6个回答

3

这将取决于代码的分布。如果有足够少的不同代码，你可以使用映射在核心中构建频率分布。否则，您可能需要构建直方图，然后对数据进行多次遍历，检查每个桶中代码的频率。

- rtayek

1

不，流式/草图算法的整个重点在于你无法保留直方图，因为数据太庞大了。 - ShreevatsaR

他/她谈论使用多次遍历来查找具有高计数的区间 - 我的问题只是那将需要多少次遍历。 - Gwildore

如果您的桶（bin）大小足够大，那么您应该能够构建直方图：http://en.wikipedia.org/wiki/Histogram#Number_of_bins_and_width - Ray Tayek

2

在内存中按照外部排序的方式对文件块进行排序。然后，不必将每个已排序代码都写入每个块中，而是只需写入每个不同的代码及其在该块中出现的次数。最后，合并这些汇总记录以找到每个代码的出现次数。

这个过程可扩展到任意大小的数据，并且它只对输入数据进行一次遍历。可能需要多次合并处理，具体取决于您想一次打开多少个汇总文件。

通过对文件进行排序，可以使用固定量的内存计算每个代码的出现次数，而无论输入大小如何。

您还知道每个代码的总数（可以通过将输入大小除以固定代码大小或通过在更普遍的问题的排序过程中计算变长代码的数量来完成）。

因此，您知道与每个代码相关联的输入比例。

这基本上就是sort * | uniq -c的管道。

如果每个代码仅出现一次，那么没有问题。您只需要能够计算它们的数量。

- erickson

如果每个代码仅出现一次，那么您的合并步骤无法取得任何进展，对吗？ - Gwildore

1

这取决于存在多少不同的代码以及可用的内存量。

我的第一个想法是构建一个计数器的哈希表，以代码作为键。循环遍历整个文件，增加相应代码的计数器，并计算总数。最后，过滤所有计数器超过（*总计数器1/200）的键。

- Harleqin

我没有足够的内存来处理这个 - 理论上每段代码都可能是不同的。 - Gwildore

1

如果文件仅由16字节代码组成，并且您知道每个文件的大小，那么您可以计算每个文件中代码的数量。然后，您可以找到0.5％的阈值，并遵循任何其他建议来计算每个代码的出现次数，记录每个频率超过阈值的代码。

- Adam Liss

1

每个文件的内容是否代表单个数据集，还是文件之间存在任意截止点？如果是后者，并且假设代码在时间上分布相对稳定，您可以通过将每个文件拆分为更小、更易管理的块来简化生活。作为奖励，您将更快地获得初步结果，并可以更早地将其管道化到下一个流程中。

- Adam Liss

我可以在数据收集时完成它，但我确实希望对整个50GB文件得出正确的答案。 - Gwildore

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Darius Bacon · Accepted Answer

Metwally等人，数据流中频繁和前k个元素的高效计算(2005)。我在雅虎工作时阅读了一些其他相关论文，但现在无法找到；但这看起来是一个不错的开端。

编辑: 啊，看看这篇Brian Hayes文章。它概述了Demaine等人的精确算法，并提供参考文献。它使用很少的内存进行一次通过，如果存在，就产生包括您正在寻找的频繁项在内的一组项目。获取精确计数需要进行第二遍(现在可处理)。