可扩展的 seq -> groupby -> 计数
Scalable seq -> groupby -> count
我有一个非常大的无序 int64 序列 - 大约 O(1B) 个条目。我需要生成元素的频率直方图，即：
inSeq
|> Seq.groupBy (fun x->x)
|> Seq.map (fun (x,l) -> (x,Seq.length l))
假设我只有 1GB 的 RAM 可以使用。完整的结果地图不适合 RAM（我也不能在 RAM 中动态构建它）。所以，我们当然必须在磁盘上生成结果。生成结果的一些高效方法是什么？
我尝试过的一种方法是对输入值的范围进行分区，并通过多次传递数据来计算每个分区内的计数。这工作正常，但我想知道我是否可以在一次通过中更快地完成它。
最后一点是频率是幂律分布的。即列表中的大多数项目只出现一次或两次，但极少数项目的计数可能超过 100k 或 1M。这表明可能维护某种 LRU 映射，其中常见项目保存在 RAM 中，不常见项目转储到磁盘。
F# 是我的首选语言，但我可以使用其他语言来完成工作。
如果您有足够的磁盘 space 来存储输入数据的副本，那么您的多次传递想法实际上只需要两次。在第一遍中，读取一个元素 x 并将其附加到临时文件 hash(x) % k，其中 k 是分片的数量（使用足以使第二遍成为可能）。在第二遍中，对于每个临时文件，使用主内存计算该文件的直方图并将该直方图附加到输出。相对于您的数据大小，1 GB 的主内存应该足够缓冲 space，其成本大约是读写数据两次的成本。
我有一个非常大的无序 int64 序列 - 大约 O(1B) 个条目。我需要生成元素的频率直方图，即：
inSeq
|> Seq.groupBy (fun x->x)
|> Seq.map (fun (x,l) -> (x,Seq.length l))
假设我只有 1GB 的 RAM 可以使用。完整的结果地图不适合 RAM（我也不能在 RAM 中动态构建它）。所以，我们当然必须在磁盘上生成结果。生成结果的一些高效方法是什么？ 我尝试过的一种方法是对输入值的范围进行分区，并通过多次传递数据来计算每个分区内的计数。这工作正常，但我想知道我是否可以在一次通过中更快地完成它。
最后一点是频率是幂律分布的。即列表中的大多数项目只出现一次或两次，但极少数项目的计数可能超过 100k 或 1M。这表明可能维护某种 LRU 映射，其中常见项目保存在 RAM 中，不常见项目转储到磁盘。
F# 是我的首选语言，但我可以使用其他语言来完成工作。
如果您有足够的磁盘 space 来存储输入数据的副本，那么您的多次传递想法实际上只需要两次。在第一遍中，读取一个元素 x 并将其附加到临时文件 hash(x) % k，其中 k 是分片的数量（使用足以使第二遍成为可能）。在第二遍中，对于每个临时文件，使用主内存计算该文件的直方图并将该直方图附加到输出。相对于您的数据大小，1 GB 的主内存应该足够缓冲 space，其成本大约是读写数据两次的成本。