k-wayマージアルゴリズム

コンピュータ サイエンスにおいて、k方向マージ アルゴリズムまたはマルチウェイ マージは、k 個のソート済みリストを取り込み、それらを 1 つのソート済みリストにマージすることに特化した、特定の種類のシーケンス マージ アルゴリズムです。これらのマージ アルゴリズムは、通常、2 つ以上のソート済みリストを取り込むマージ アルゴリズムを指します。2 方向マージは、バイナリ マージとも呼ばれます。k 方向マージは、外部ソート アルゴリズムでもあります。

2 方向マージ、またはバイナリ マージは、マージ ソートにおける重要な役割のため、広範囲に研究されてきました。その一例は、マージ ソートの例で頻繁に登場するクラシック マージです。クラシック マージは、各ステップでキーが最も低いデータ項目を出力します。ソートされたリストがいくつか与えられると、入力リストのいずれかのすべての要素を含むソートされたリストを生成します。これは、入力リストの長さの合計に比例した時間で行われます。

A[1..p]とB[1..q]で昇順にソートされた2つの配列を表します。さらに、出力配列をC[1..n]で表します。標準的な2方向マージアルゴリズム^[1]は、インデックスi、j、kをそれぞれA、B、Cに格納します。最初、これらのインデックスは最初の要素を参照します。つまり、1です。A[i] < B[j]の場合、アルゴリズムはA[i]をC[k]にコピーし、iとkを増やします。それ以外の場合、アルゴリズムはB[j]をC[k]にコピーし、jとkを増やします。iまたはjがAまたはBの末尾に到達した場合は特別なケースが発生します。この場合、アルゴリズムはBまたはAの残りの要素をCにコピーして終了します。

k方向のマージ問題は、k 個のソート済み配列をマージして、同じ要素を持つ単一のソート済み配列を生成することです。要素の総数を n で表します。n は、出力配列のサイズと k 個の入力配列のサイズの合計に等しくなります。簡単にするために、入力配列はどれも空ではないと仮定します。結果として、報告される実行時間が簡略化されます。この問題は、実行時間とスペースで解決できます。この実行時間を実現するアルゴリズムはいくつか存在します。 ${\displaystyle k\leq n}$${\displaystyle {\mathcal {O}}(n\cdot \log(k))}$${\displaystyle {\mathcal {O}}(n)}$

この問題は、2 方向マージを使用して k 個の配列のうち 2 つを繰り返しマージし、1 つの配列だけが残るようにすることで解決できます。配列が任意の順序でマージされた場合、結果として得られる実行時間は O(kn) のみです。これは最適ではありません。

実行時間は、最初のものを 2 番目と、3 番目を 4 番目と、というように繰り返しマージすることで改善できます。各反復で配列の数が半分になるため、反復回数は Θ(log k) 回のみです。各反復で、すべての要素が 1 回だけ移動されます。したがって、反復あたりの実行時間は Θ(n) で表されます (n は要素数)。したがって、合計実行時間は Θ(n log k) です。

このアルゴリズムは、2 つの最短配列を繰り返しマージすることでさらに改善できます。これにより実行時間が最小化され、前の段落で説明した戦略よりも悪くならないことは明らかです。したがって、実行時間は O(n log k) です。幸い、境界ケースでは実行時間が改善される可能性があります。たとえば、1 つの配列を除くすべての配列に 1 つの要素のみが含まれる退化したケースを考えてみましょう。前の段落で説明した戦略では Θ(n log k) の実行時間が必要ですが、改善された戦略では Θ(n + k log k) の実行時間しか必要ありません。

この場合、k 実行を同時にマージします。

単純な実装では、すべての k 配列をスキャンして最小値を決定します。この単純な実装では、実行時間は Θ(kn) になります。これは、説明のために可能性としてのみ言及されていることに注意してください。これは機能しますが、効率的ではありません。

最小要素をより速く計算することで、これを改善できます。ヒープ、トーナメント ツリー、またはスプレイ ツリーのいずれかを使用すると、最小要素を O(log k) 時間で決定できます。したがって、結果として得られる実行時間は O(n log k) になります。

ヒープの方が一般的に使用されていますが、実際にはトーナメント ツリーの方が高速です。ヒープは、ツリーをルートから一番下まで処理し、各ノードの両方の子を比較する必要があるため、各ステップで約 2*log(k) 回の比較を使用します。一方、トーナメント ツリーは、ツリーの一番下から開始してルートまで処理し、各レイヤーで 1 回の比較のみを行うため、log(k) 回の比較のみが必要です。したがって、トーナメント ツリーが推奨される実装です。

アイデアは、k 個のリストからなる最小ヒープを維持することです。各リストは、現在の最小要素をキーとします。単純なアルゴリズムによって、ヒープからのノードを含む出力バッファが作成されます。まず、ノードの最小ヒープを作成します。各ノードは、リストの先頭要素と、リストの残り (または末尾) で構成されます。リストは最初にソートされるため、先頭は各リストの最小要素です。ヒープ プロパティにより、ルートにはすべてのリストの中で最小の要素が含まれることが保証されます。ヒープからルート ノードを抽出し、先頭要素を出力バッファに追加し、末尾から新しいノードを作成して、ヒープに挿入します。ヒープにノードが 1 つだけ残るまで繰り返します。その時点で、残りのリスト (先頭と末尾) を出力バッファに追加します。

インプレースヒープアルゴリズム ^[2]は、ポインタを使用して、 入力配列にポインタの最小ヒープを割り当てます。最初、これらのポインタは入力配列の最小要素を指します。ポインタは、指している値によってソートされます。O(k)の前処理ステップでは、標準のヒープ化手順を使用してヒープが作成されます。その後、アルゴリズムはルートポインタが指す要素を反復的に転送し、このポインタを増やして、ルート要素に対して標準のキー減少手順を実行します。キー増加手順の実行時間は、O(log k) に制限されます。要素がn個あるため、合計実行時間はO(n log k)です。

キーを置き換え、キーの減少またはシフトダウンを反復的に実行する操作は、C++ stl や Java などの多くの Priority Queue ライブラリではサポートされていないことに注意してください。抽出最小化と挿入関数を実行するのは効率が悪くなります。

トーナメントツリー^[3]は、スポーツ競技のようなトーナメントに基づいています。各ゲームでは、入力要素のうち2つが競い合います。勝者は次のラウンドに進みます。したがって、ゲームのバイナリツリーが得られます。リストは昇順で並べ替えられているため、ゲームの勝者は両方の要素の小さい方になります。

k 方向マージでは、各ゲームの敗者のみ保存する方が効率的です (画像を参照)。したがって、データ構造は敗者ツリーと呼ばれます。ツリーを構築したり、要素をリストの次の要素に置き換えたりするとき、ゲームの勝者を一番上に昇格させます。ツリーはスポーツの試合のように埋められますが、ノードには敗者のみ保存されます。通常、ルートの上には、全体の勝者を表す追加のノードが追加されます。すべてのリーフには、入力配列の 1 つへのポインターが格納されます。すべての内部ノードには、値とインデックスが格納されます。内部ノードのインデックスは、値がどの入力配列からのものかを示します。値には、対応する入力配列の最初の要素のコピーが含まれます。

アルゴリズムは、最小要素を結果に繰り返し追加し、対応する入力リストから要素を削除します。更新されたリーフからルートへのパス上のノードを更新します (置換選択)。削除された要素は、全体的な勝者です。したがって、入力配列からルートへのパス上の各ゲームに勝利しています。入力配列から新しい要素を選択する場合、要素はルートへのパス上の以前の敗者と競争する必要があります。敗者ツリーを使用する場合、ゲームを再プレイするためのパートナーはノードにすでに格納されています。再プレイされた各ゲームの敗者はノードに書き込まれ、勝者は反復的にトップに昇格されます。ルートに到達すると、新しい全体的な勝者が見つかり、次のマージラウンドで使用できます。

このセクションのトーナメント ツリーと敗者ツリーの画像は同じデータを使用しており、比較することで敗者ツリーの動作を理解することができます。

トーナメント ツリーは、入力リストにセンチネルを追加し (つまり、各リストの末尾に無限大の値を持つメンバーを追加)、リストの数が 2 の累乗になるまでヌル リスト (センチネルのみで構成) を追加することで、バランスの取れたバイナリ ツリーとして表すことができます。バランスの取れたツリーは、単一の配列に格納できます。親要素に到達するには、現在のインデックスを 2 で割る必要があります。

リーフの 1 つが更新されると、リーフからルートまでのすべてのゲームが再プレイされます。次の疑似コードでは、理解しやすいように、配列ではなくオブジェクト指向ツリーが使用されています。また、マージするリストの数は 2 の累乗であると想定されています。

関数merge(L1, ..., Ln)
    buildTree(L1、...、Lnの先頭)
    ツリーには要素があるが
        勝者 := tree.winner
        出力winner.value
        新しい := 勝者.インデックス.次
        replayGames(winner, new) // 置換選択

関数replayGames(ノード、新規)
    敗者、勝者 := playGame(node, new)
    ノード値:= 敗者値
    ノード.インデックス:=敗者.インデックス
    ノード != ルートの場合
        replayGames(node.parent, 勝者)

関数buildTree(要素)
    次のレイヤー:=新しい配列()
    要素が空でないとき
        el1 := 要素.take()
        el2 := 要素.take()
        敗者、勝者 := playGame(el1, el2)
        親 := 新しいノード(el1, el2, loser)
        次のレイヤーを追加します(親)
    if nextLayer.size == 1
         return nextLayer // ルートのみ
    else 
        return buildTree(nextLayer)

まず、ツリーはΘ(k)の時間で作成されます。マージの各ステップでは、新しい要素からルートへのパス上のゲームのみを再生する必要があります。各レイヤーでは、1つの比較のみが必要です。ツリーはバランスが取れているため、入力配列の1つからルートへのパスにはΘ(log k)要素のみが含まれます。合計で、転送する必要がある要素はn個あります。したがって、結果として得られる合計実行時間はΘ(n log k)になります。^[3]

次のセクションには、置換選択手順の詳細な例と、複数の置換選択を含む完全なマージの例が 1 つ含まれています。

ゲームは下から上に向かって再生されます。ツリーの各レイヤーでは、ノードに現在格納されている要素と、下のレイヤーから提供された要素が競合します。新しい総合優勝者が見つかるまで、勝者は最上位に昇格します。敗者はツリーのノードに格納されます。

マージ自体を実行するには、全体の最小要素を次の入力要素に繰り返し置き換えます。その後、トップまでのゲームが再プレイされます。

この例では、4 つのソートされた配列を入力として使用します。

{2、7、16}
{5、10、20}
{3、6、21}
{4、8、9}

アルゴリズムは、各入力リストの先頭から開始されます。これらの要素を使用して、敗者のバイナリ ツリーが構築されます。マージでは、ツリーの最上部にある全体的な最小要素を見て、リストの最小要素 2 が決定されます。次にその値がポップオフされ、そのリーフが入力リストの次の値である 7 で補充されます。トップまでのゲームは、前のセクションの置換選択と同様に再プレイされます。削除される次の要素は 3 です。リストの次の値である 6 から始めて、ルートまでゲームが再プレイされます。これは、ツリーの最小値が無限大になるまで繰り返されます。

実行時間がO ( n f(k)) の比較ベースのk方向マージ アルゴリズムは存在しないことが示されます。ここで、 f は対数よりも漸近的に遅くなり、n は要素の総数です (分離した範囲などの望ましい分布を持つデータは除きます)。証明は、比較ベースのソートからの直接的な還元です。そのようなアルゴリズムが存在すると仮定すると、実行時間がO ( n f( n )) の比較ベースのソート アルゴリズムを次のように構築できます。入力配列をサイズ 1 の n 個の配列に分割します。これらの n 個の配列をk方向マージ アルゴリズムでマージします。結果の配列はソートされ、アルゴリズムの実行時間はO ( n f( n )) です。これは、最悪の場合の実行時間がO ( n log n ) 未満の比較ベースのソート アルゴリズムは存在しないというよく知られた結果と矛盾しています。

k方向マージは外部ソート手順で使用されます。^[4] 外部ソートアルゴリズムは、大量のデータを処理できるソートアルゴリズムの一種です。ソートするデータがコンピューティングデバイスのメインメモリ (通常は RAM) に収まらず、代わりに低速の外部メモリ (通常はハードドライブ) に格納する必要がある場合に、外部ソートが必要になります。k方向マージアルゴリズムは通常、マージソートの場合と同様に、外部ソートアルゴリズムの第 2 段階で実行されます。

マルチウェイ マージでは、メモリ外のファイルをバイナリ マージよりも少ないパスでマージできます。マージする必要がある実行が 6 つある場合、バイナリ マージでは 3 つのマージ パスが必要になりますが、6 ウェイ マージでは 1 つのマージ パスで済みます。このマージ パスの削減は、通常最初にソートされる大量の情報を考慮すると特に重要であり、速度が大幅に向上すると同時に、低速ストレージへのアクセス量も削減されます。