algorithm - 可扩展的 seq -> groupby -> 计数

Question

我有一个非常大的无序 int64 序列——大约 O(1B) 个条目。我需要生成元素的频率直方图，即:

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

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

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

F# 是我的首选语言，但我可以使用其他语言来完成工作。

Answer 1

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