穩定排序一個巨大的文件

Question

我想排序列上的一個巨大的文件。排序應該穩定。目前，我正在使用unix排序（使用-s選項）。但速度很慢。有沒有衆所周知的例程在hdfs中做到這一點？

我試過PIG的orderby但是不穩定。

Answer 1

我會將文件拆分成塊（您可以在命令行上做到這一點，但它取決於數據;您可能需要一個程序來做到這一點）。塊的大小取決於你（幾兆字節是好的;確保unix排序快一塊）。

然後使用unix排序每個塊（sort -s -k...）。如果你有多臺機器，你可以並行進行。

然後使用unix排序合併所有排序的塊（sort -m -k...）。如果按照正確的順序指定文件列表，這應該也是穩定的。如果不是（我沒有測試，也沒有找到任何信息，但很可能它是穩定的），那麼你可能需要編寫你自己的合併程序，這應該不是很複雜。

如果有太多的塊有效合併，可以將塊1..10合併爲一塊，然後將塊11..20合併到塊b（再次可以在多臺機器上並行執行），最後合併塊a..z。但我懷疑這是真的需要。

Answer 2

如果該文件是巨大的，您可以編寫使用std::stable_sort

一些C++11程序，以便大於可用RAM越大，你可以考慮選塊，將它們合併。