8

n-way マージに関する記事をいくつか読もうとしましたが、概念がわかりませんでした。2方向マージよりもn方向マージを使用する理由について混乱していますか? なぜ配列を3つの部分に分割し、それらを並べ替えてから、2つの部分を2方向にマージし、次に3番目の部分をこの2つの部分に2方向にマージします:)

ありがとう

4

2 に答える 2

15

通常、外部ソートを行っている場合、複数のストリームをマージすることになります。たとえば、1 テラバイトのデータを並べ替える必要があり、(たとえば) 64 ギガバイトの RAM しかないとします。

通常は、64 ギガバイトを読み取り、並べ替えてから書き出すことで、これを行います。一度にメモリに保持できる「チャンク」ごとに 1 つの中間ファイルを生成して、テラバイトのデータ全体に対して繰り返します。これを改善する方法はいくつかありますが、一般的に期待できる最良の方法は、それぞれ約 128 ギガバイトのソート済み中間ファイルを生成することです。

これにより、いくつかの中間ファイルがマージされて残ります。その数はほぼ確実に 2 より大きくなります。

定期的にこれを行う場合は、かなりハイエンドのハードウェアを使用している可能性があります。各中間ファイルを別々のディスク ドライブに置いた場合 (出力用に少なくとも 1 つ以上ある場合)、一度に 2 つだけではなく、すべてのデータを一度にマージすることで、ほぼ確実に速度を向上させることができます。プロセスは通常 I/O バウンドであるため、一度に 8 つのディスクから読み取ると、一度に 2 つのディスクからのみ読み取る場合よりも約 4 倍速くなります (ただし、これは出力ディスクの帯域幅によって異なります)。 、これは正しくない可能性があります)。より多くの中間ファイルを作成しないようにすることで (さらにマージが必要になります)、全体的な速度はおそらくさらに大きく改善されます。

于 2013-02-05T17:55:46.627 に答える
12

「通常の」マージソートでは、深さに達するまで配列を2で除算してから、マージを開始します。サイズの2つの配列をマージするたびに、操作も必要になります。log2nm2m

これにより、次の式が得られます（タイミング分析）。

n / 2 * 2 + n / 4 * 4 + ... 1 * n = n * log 2 n

ここで、3方向マージを実行する場合、配列を3で除算します。前の方法との違いは2つあります。

  • 分割の深さは現在です。log3n
  • マージ中に、2つの要素を比較する代わりに、最低3つの要素を見つける必要があります。

これは、最も基本的な実装では、次の式が得られることを意味します。

n / 3 * 2 * 3 + n / 9 * 2 * 9 + ... 1 * 2 * n = 2 * n * log 3 n

最小の3つの要素を見つけることは2つの操作で構成されるため、2が乗算されることに注意してください。

漸近的に、これら2つは両方ともΘ(nlogn)です。ただし、おそらく（私は試していませんが）実際には、3方向マージソートの方がパフォーマンスが向上します。それにもかかわらず、n = 1000000の場合はわずか20であり、同じ数の場合は12.5であるため、この最適化が非常に大きくない限り、本当に効果的であるとは思えません。log3nlog2nlog3nn

巧妙な実装により、k-wayマージは実際にマージソートに素晴らしい影響を与える可能性があります。最小の要素を見つけたら、最小ではないk残りの要素間の関係をすでに知っているという考え方ですk-1。したがって、それぞれのリストからその最小要素を消費したら、そのリストの新しい値を比較し、残りのk-1要素に関する順序を見つけるだけで済みます。ヒープを使用すると、これは非常に簡単です。

ジェリーの答えも必ず見てください。マルチウェイマージの真の力は、複数のディスクと並列処理を処理することから生まれることに同意します。

于 2013-02-05T17:54:09.210 に答える