[解決済み] 効率的なアウトオブコアソーティング

質問

メモリに収まらない巨大なデータセットを効率的にソートする方法を考えています。 高レベルでの明白な答えは、ある標準的なアルゴリズムを使ってメモリに収まる塊の全体をソートし、それらをディスクに書き出し、そしてそれらをマージすることです。 マージすることが問題なのです。

例えば、データがC個のチャンクに分かれていて、マージするのはC個のファイルだとします。 もし私が1パスでC-wayマージを行うなら、技術的にはO(N^2)アルゴリズムになりますが、ディスクへの書き込みはO(N)回で済みます。 もし私がそれらをC/2ファイル、C/4ファイルなどに繰り返しマージするなら、O(N log N)アルゴリズムになりますが、ディスクへの書き込みをO(N log N)回行わなければならず、その結果、以下のような問題が発生します。 巨大 定数項

この難問に対する典型的な解答は何でしょうか？ 何かいい方法はないでしょうか？

どのように解決するのか？

単純に言えば、この問いに単純な答えはないということです。多くの答えがありますが、そのほとんどはかなり複雑です -- Knuthの第3巻(一例)では、この問題に多くのスペースを割いています。

これまでに行われたことに目を通すと、明らかになることがあります。 本当に 最初のソートで作成するランの数を最小限にし、それぞれのランの長さを最大にしたいのです。そのためには、一般にメモリに収まる程度のデータを読み込みますが、単にソートして書き出すのではなく、ヒープに格納するようにしたいものです。そして、各レコードを書き出すと同時に、別のレコードを読み込むのです。

そして、そのレコードが先ほど書き出したレコードの前か後かでソートされるかどうかをチェックします。もし後にソートされるなら、それをヒープに挿入し、続行します。もしそのレコードが前にソートされるなら、それを2番目のヒープに挿入する。

最初のヒープが完全に空になり、2番目のヒープがすべてのメモリを消費するようになったら、現在のランへのレコードの追加を停止します。この時点で、このプロセスを繰り返し、新しいファイルに新しい実行を書き込みます。

この場合、通常、初期段階ではかなり長い中間ランが作成されるため、それらをマージすることで大幅に作業が軽減されます。しかし、入力レコードが部分的にでもソートされていれば、既存の順序を利用して実行時間をさらに長くすることができる。

余談ですが、これは私が発明したわけではなく、おそらく最初に読んだのはKnuthで、おそらくは アルゴリズム＋データ構造＝プログラム (Niklaus Wirth)の両者で議論されています。Knuthは、このメソッドを最初に発表したのは"H. Seward"が1954年にMITの修士論文で発表したものであるとしています。Knuthの第2版を持っていれば、第3巻の254ページに載っています。私は第3版を持っていないので、そのページ番号はわかりません。