なぜn-wayマージを使うべきですか？ 2ウェイマージよりもメリットは何ですか？

Question

私はn-wayマージでいくつかの記事を読むことを試みましたが、その概念を理解していませんでした。私は2-wayマージでn-wayマージを使用する理由について混乱していますか？なぜあなたは彼らがその後、2部の2ウェイマージを行い、その後、これに第3部の2ウェイマージは2部:)

おかげで、「通常で

Answer 1

をマージソートし、3部の配列を分割するのと同じよう"マージソートでは、配列を2で除算し、深さがlog2nに達するまでマージを開始します。サイズがmの2つの配列の各マージは、2mの操作をとることになります。

これは、（解析タイミングで）、次の式にあなたを取得します。

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

を今、あなたは3ウェイマージを行う場合は、従来の方法との違いは2つあり3で配列を分割します：

• ここで、分割の深さはlog3nです。
• マージ中に、2つの要素を比較する代わりに、最低3つの要素を見つける必要があります。三つの要素の最小値を見つけること2つの操作で構成されているので2が乗算され

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

  注こと：

これは、最も基本的な実装では、このような式を得るだろう、ということを意味します。

漸近的には、これら2つはともにΘ(nlogn)です。しかし、おそらく（私は試していない）実際には、その3つの方法のマージソートは、log3nのため、より良いパフォーマンスを与えるだろう。それにもかかわらず、n = 1000000のlog2nはわずか20であり、同じ番号のlog3nは12.5なので、nが非常に大きい場合を除き、この最適化は実際には有効ではないでしょうか。

---

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

---

Jerry's answerも必ず参照してください。私は、マルチウェイマージの真のパワーは、複数のディスクや並列処理を扱うことから来ていると彼に同意します。

Answer 2

通常、外部の並べ替えを行うときにマージする複数のストリームになります。たとえば、テラバイトのデータをソートし、64ギガバイトのRAMしか持たないと仮定します。

通常、64ギガバイトで読み込み、ソートして書き出します。 1テラバイト分のデータを繰り返して、一度にメモリに保持できる各 "チャンク"ごとに1つの中間ファイルを作成します。これを改善する方法はありますが、通常は約128ギガバイトのソートされた中間ファイルを作成することが一般的には可能です。そして数はほぼ確実にあなたが定期的にこれを行うためにやっている場合、あなたはおそらく、いくつかを持っている2.

より大きくなります - 一緒にマージする中間ファイルの数であなたを残し

かなりハイエンドのハードウェアでそれを行う。各中間ファイルを別々のディスクドライブに入れて（少なくとも1つ以上を出力する場合）、すべてのデータを一度に2つではなく一度にまとめて、ほぼ確実に速度を向上させることができます。プロセスは一般的にI/O境界になりますので、一度に8個のディスクを読み取る（たとえば）ディスクは、一度に2つのディスクから読み取るのに比べて通常約4倍高速です（ただし、これは真実ではない可能性があります）。より多くの中間ファイルを作成しないようにすると（それ以上のマージが必要になります）、全体的なスピードはおそらくさらに大きな要素によって向上します。