linux - 稳定排序一个巨大的文件

Question

我想在一列上对一个大文件进行排序。排序应该是稳定的。目前，我正在使用 unix 排序（带有 -s 选项）。但这很慢。在 hdfs 中是否有众所周知的例程来执行此操作？

我尝试了 PIG 的 orderby，但不稳定。

Answer 1

我会将文件拆分成块（您可能可以在命令行上执行此操作，但这取决于数据；您可能需要一个程序来执行此操作）。块大小由您决定（几兆字节就可以了；确保 unix 排序对于一个块来说是快速的）。

然后使用 unix sort ( sort -s -k...) 对每个块进行排序。如果您有多台机器，则可以并行执行。

然后使用 unix sort ( ) 合并所有已排序的块sort -m -k...。如果您以正确的顺序指定文件列表，这也应该是稳定的。如果不是（我没有对此进行测试并且没有找到任何信息，但很可能它是稳定的），那么您可能需要编写自己的合并程序，这应该不是很复杂。

如果您有太多块无法有效合并，您可以将块 1..10 合并到块 a，然后将块 11..20 合并到块 b（同样，您可以在多台机器上并行执行此操作），最后合并块a..z。但我怀疑这是否真的需要。

Answer 2

您可以使用std::stable_sort编写一些C++11程序

如果文件很大，因此大于可用 RAM，您可以考虑对块进行排序并合并它们。