可擴展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 - >計數

回答

相關問題