データがメモリに収まらない場合に Unix で巨大なファイルをソートするというトピックについて、Web 上で多くの議論があります。通常、マージソートとバリアントを使用します。
ただし、データ全体を収めるのに十分なメモリがあったとしたら、最も効率的/最速の並べ替え方法は何でしょうか? csv ファイルは最大 50 GB (> 10 億行) で、データ全体を保持するのに十分なメモリ (データのサイズの 5 倍) があります。
Unix ソートを使用できますが、それでも 1 時間以上かかります。必要な言語は何でも使用できますが、主に求めているのは速度です。データを列型のデータベーステーブルとソートにロードできることは理解していますが、それは1回限りの作業なので、もっと機敏なものを探しています...
前もって感謝します。
大量のデータには並列ソート アルゴリズムを使用します。
役に立つトピック: どの並列ソート アルゴリズムが最高の平均ケース パフォーマンスを持っていますか?
クイックソートはどうですか？試しましたか？std::sort は通常、クイックソート (より正確には、クイックソートのパフォーマンスが悪い場合にヒープソートに切り替える introsort) によって実装されるため、試してみることができます。通常はクイックソートが最速のオプションです (ただし、最悪の場合の複雑さは O(n^2) ですが、通常は他のすべてのソート アルゴリズムよりも優れています)。
クイックソートのスペースの複雑さはそれほど悪くないはずです。log2(N) のスタックスペースが必要です。これは、10 億のアイテムに対して約 30 スタックフレームです。
ただし、ソート アルゴリズムが不安定 (「等しい」アイテムの順序が保持されない) であるため、それで問題ないかどうかに依存します。
ところで。Unix ソートはマージソートによって実装されているようですが、これは通常、イン RAM ソートの最速のオプションではありません。