可扩展seq - > groupby - >计数

我有一个非常大的无序序列int64s - 关于O（1B）条目。我需要生成元素的频率直方图，即：可扩展seq - > groupby - >计数

inSeq 
|> Seq.groupBy (fun x->x) 
|> Seq.map (fun (x,l) -> (x,Seq.length l))

让我们假设我只有1GB的内存可用。完整的结果地图不适合RAM（也不能在RAM中实时构建）。所以，我们当然必须在磁盘上生成结果。什么是生成结果的一些高性能方法？我尝试过的一种方法是对输入值的范围进行分区，并通过数据的多次传递来计算每个分区内的计数。这工作正常，但我想知道如果我能在一次传递中更快完成它。

最后一点是频率是幂律分布的。即列表中的大多数项目只出现一次或两次，但是很少数量的项目可能会超过100k或1M。这表明可能会维护某种类型的LRU映射，其中公用项目被保存在RAM中，而不常见的项目被转储到磁盘。

F＃是我的首选语言，但我可以用别的方法来完成工作。

来源

2015-02-08 Robert Sim

对于每个键，“Seq.groupBy”将存储大量等价值序列，在下一步将丢弃*。为什么不使用可变[ConcurrentDictionary]（https://msdn.microsoft.com/en-us/library/dd287191%28v=vs.100%29.aspx）来计算* number *的元素，而不是元素本身？这将是一个非常简单的O（n）算法。 – bytebuster 2015-02-09 00:19:25

当然'Seq.countBy'在这里会很不错 – 2015-02-09 00:23:52

我们正在计算一个字典（值，计数值）。我们正在谈论一棵1e9叶*每叶16字节的树。方式超过1GB。结果必须缓存到磁盘，否则我们会疯狂地肆虐。 [编辑]在unix-land中，我们称sort | uniq -c。当流变得巨大时，Unix排序非常聪明。也许正确的做法是使用磁盘对元素进行排序，然后我们可以对已排序的集合进行流式处理以产生计数流。 – 2015-02-09 00:54:34

如果您有足够的磁盘空间作为输入数据的副本，那么您的多次传递构思确实只需要两个。在第一遍中，读取一个元素x并将其附加到临时文件hash(x) % k，其中k是碎片的数量（仅用于足以使第二遍可能）。在第二遍中，对于每个临时文件，使用主存储器计算该文件的直方图并将该直方图附加到输出。相对于你的数据的大小，一个千兆字节的主内存应该有足够的缓冲空间，这个成本大约是两次读写数据的成本。

来源

2015-02-09 01:39:13

谢谢，我喜欢这个选项。我正在研究一个[外部排序]（http://en.wikipedia.org/wiki/External_sorting），然后是一个单独的传递，但是这个选项限制了排序到分片内部，可能为我节省了一个传球。 – 2015-02-09 07:55:20

可扩展seq - > groupby - >计数

回答

相关问题