大きなファイルを外部でマージソートする場合、それを小さなファイルに分割し、それらをソートしてから、それらを大きなソート済みファイルにマージします。
マージするときは、多数の双方向マージ パスを実行するか、1 つの多方向マージ パスを実行できます。
どのアプローチが良いのだろうか？なぜ？
3066 次
1 に答える
7
一般に、1 つの多方向マージの方が優れています。次の 3 つの小さなファイルについて考えてみましょう。
a1
a2
a3
と
b1
b2
b3
そして最後に
c1
c2
c3
と をマージするaとb、(たとえば) が残ります。
a1
b1
a2
b2
b3
a3
と
c1
c2
c3
最終的なマージはソートされたリストを作成しますが、この最終的なマージでどのようにアイテムにアクセスしなければならないかに注意してaくださいb。双方向マージをカスケードする際に無駄になるのは、この再マージです。
代わりにできることは、単一の多方向マージです。ただし、やり方には気をつけてください。具体的には、各カーソルをスキャンして最小値を持つカーソルを確認する単純な二重ループを回避します。代わりに最小ヒープを使用してください。これにより、複雑さが に戻りO(n log n)ます。
于 2012-08-04T06:39:32.773 に答える