マージアルゴリズム

マージアルゴリズムは、複数のソート済みリストを入力として受け取り、入力リストのすべての要素をソートされた順序で含む単一のリストを出力するアルゴリズム群です。これらのアルゴリズムは、さまざまなソートアルゴリズムのサブルーチンとして使用され、最も有名なのはマージソートです。

応用

マージアルゴリズムは、比較に基づくソートアルゴリズムであるマージソートアルゴリズムにおいて重要な役割を果たします。概念的には、マージソートアルゴリズムは次の2つのステップで構成されます。

リストを（ほぼ）等しい長さのサブリストに再帰的に分割し、各サブリストに要素が1つだけ含まれるまで繰り返します。反復（ボトムアップ）マージソートの場合は、 n個の要素を持つリストを、サイズ1のn個のサブリストとみなします。要素が1つだけ含まれるリストは、定義上、ソート済みです。
サブリストを繰り返しマージして、すべての要素を含む単一のリストを作成するまで、ソート済みの新しいサブリストを作成します。作成された単一のリストが、ソート済みのリストです。

マージアルゴリズムは、マージソートアルゴリズムの中で繰り返し使用されます。

図には、マージソートの例が示されています。まず、7つの整数からなる未ソート配列を用意します。この配列を7つのパーティションに分割し、各パーティションには1つの要素を含めてソートします。次に、ソートされたパーティションをマージして、より大きなソート済みパーティションを作成し、最終的に1つのパーティション（ソート済みの配列）が残るまでこの処理を繰り返します。

2つのリストをマージする

2 つのソート済みリストを 1 つにマージすることは、線形時間と線形または定数空間 (データアクセスモデルによる)で実行できます。次の擬似コードは、入力リスト (リンクリストまたは配列) $A$ と $B$ を新しいリスト $C$ にマージするアルゴリズムを示しています。^{[ 1 ]}^{[ 2 ]}^{: 104}関数headはリストの最初の要素を返します。要素を「削除」するとは、通常はポインタまたはインデックスをインクリメントすることによって、その要素をリストから削除することを意味します。

アルゴリズムmerge(A, B)は、入力A, B : リスト を返します C := 新しい空のリスト A が空でなく、B も空でない間、 head(A) ≤ head(B)ならば、 Cにhead(A)を追加する Aの頭文字を落とす それ以外 Cにhead(B)を追加する Bの頭を落とす // この時点で、A または B のいずれかが空になっている。残りの入力リストを空にする。while A が空でない間、 Cにhead(A)を追加する Aの頭文字を落とす Bが空でない間、 Cにhead(B)を追加する Bの頭を落とす Cを返す

入力が連結リストの場合、このアルゴリズムは一定量の作業領域のみを使用するように実装できます。リストのノード内のポインタは、記録管理と最終的な結合リストの構築に再利用できます。

マージソートアルゴリズムでは、このサブルーチンは通常、単一の配列Aの2 つのサブ配列A[lo..mid]、A[mid+1..hi] をマージするために使用されます。これは、サブ配列を一時配列にコピーしてから、上記のマージアルゴリズムを適用することで実行できます。^[¹^]一時配列の割り当ては回避できますが、速度とプログラミングの容易さが犠牲になります。さまざまなインプレースマージアルゴリズムが考案されており、^[³^]線形時間境界を犠牲にして $O$ $($ $n$ $log$ $n$ $)$ アルゴリズムを生成することもあります。^[⁴^]マージソート §バリアントの説明を参照してください。

Kウェイ合流

$k$ 分割マージは、バイナリマージを任意の数 $k$ のソート済み入力リストに一般化したものです。k 分割マージの応用例 $として$ は、ペイシェンスソート^{[ 5 ]}や、入力をメモリに収まる $k$ $=$ $1$ $/$ $M$ $-$ $1 個のブロックに分割し、それらを 1 つずつソートしてからマージする$ 外部ソートアルゴリズム^[²^]^:^{119–120など、さまざまなソートアルゴリズム} $が$ 挙げられます。

この問題にはいくつかの解決策が存在する。単純な解決策としては、 $k$ 個のリストをループ処理して毎回最小の要素を選択し、すべてのリストが空になるまでこのループを繰り返す方法がある。

$入力： k$ 個のリストのリスト。
いずれかのリストが空でない場合：
- リストをループ処理して、最初の要素が最小のリストを見つけます。
- 最小要素を出力し、リストから削除します。

最悪の場合、このアルゴリズムは、リストに合計 $n個の要素がある場合$ $、$ 処理を実行するために $(k - 1)(n - k / 2)回の要素比較を実行します。$ ^[⁶^]リストを最初の要素をキーとする優先度付きキュー(最小ヒープ) に格納することで、このアルゴリズムを改善でき $ます$ 。

$k$ 個のリストの最初の要素をキーとして、最小ヒープ $hを構築する。$
いずれかのリストが空でない場合：
- $i = find-min(h)$ とする。
- $リストi$ の最初の要素を出力し、その要素をリストから削除します。
- $h$ を再ヒープします。

出力する次の最小要素の検索（find-min）とヒープ順序の復元は、 $O (log k)$ 時間（より具体的には、 $2⌊log k⌋ 回の$ 比較^{[ 6 ] ）で実行でき、}^問題 $全体はO (n log k)$ 時間（約 $2n⌊log k⌋ 回の$ 比較）で解決できる。^{[ 6 ]} $[$ ²^]^{： 119-120}

この問題に対する3つ目のアルゴリズムは、二項結合アルゴリズムを基にした分割統治法である。

$k = 1$ の場合、入力された単一のリストを出力します。
$k = 2$ の場合、バイナリマージを実行します。
そうでない場合は、最初の $⌊ k /2⌋$ リストと最後の $⌈ k /2⌉$ リストを再帰的にマージし、それらをバイナリマージします。

このアルゴリズムへの入力リストが長さ順に並べられ、短いものから順に並べられている場合、必要な比較回数は $n ⌈log k ⌉$ 未満、つまりヒープベースのアルゴリズムで使用される回数の半分以下になります。実際には、ヒープベースのアルゴリズムとほぼ同じくらいの速さまたは遅さになる可能性があります。^{[ 6 ]}

並列マージ

バイナリマージアルゴリズムの並列バージョンは、並列マージソートの構成要素として使用できます。次の擬似コードは、このアルゴリズムを並列分割統治スタイルで示しています（Cormen et al. ^[⁷^]^:⁸⁰⁰から改変）。これは、2 つのソート済み配列 $A$ と $Bに対して動作し、ソートされた出力を配列$ $C$ に書き込みます。表記A[i...j]は、インデックス $iから j までの$ $A$ の部分を表します（iと $j$ は含みません）。

アルゴリズムmerge(A[i...j], B[k...ℓ], C[p...q])は入力A, B, C : 配列 i、j、k、ℓ、p、q：インデックス m = j - iとする。 n = ℓ - k m < nの場合、 A と B を交換する // A がより大きな配列であることを確認する: i、j は引き続き A に属し、k、ℓ は B に属する mとnを入れ替える m ≤ 0の場合、以下を返す// 基本ケース、マージするものはありませんlet r = ⌊(i + j)/2⌋ let s = binary-search(A[r], B[k...ℓ]) let t = p + (r - i) + (s - k) C[t] = A[r] 並行して merge(A[i...r], B[k...s], C[p...t]) merge(A[r+1...j], B[s...ℓ], C[t+1...q])

このアルゴリズムは、 $A$ または $B$ のうち大きい方を (ほぼ) 等しい半分に分割することによって動作します。次に、もう一方の配列を、最初の配列の中間値より小さい値を持つ部分と、それより大きいか等しい値を持つ部分に分割します。 (バイナリサーチサブルーチンは、 $A$ $[$ $r$ $]が$ $B$ にある場合のB $内$ のインデックスを返します。これは常に $k$ から $ℓ$ の間の数値です。) 最後に、各半分のペアが再帰的にマージされ、再帰呼び出しは互いに独立しているため、並列に実行できます。再帰の基本ケースにシリアルアルゴリズムを使用するハイブリッドアプローチは、実際にはうまく機能することが示されています^[⁸^{] 。}

$合計n$ 個の要素を持つ 2 つの配列に対してアルゴリズムが実行する作業、つまりその逐次バージョンの実行時間は $O$ $($ $n$ $)です。n 個$ $の要素を$ $C$ にコピーする必要があるため、これは最適です。アルゴリズムのスパンを計算するには、漸化式を導出する必要があります。merge の 2 つの再帰呼び出しは並列であるため、 2 つの呼び出しのうちコストの高い方のみを考慮すれば十分です。最悪の場合、再帰呼び出しの 1 つに含まれる要素の最大数は、最大で $\textstyle {\frac {3}{4}}n}$ 要素数の多い配列は完全に半分に分割されるため、 $\Theta \left(\log(n)\right)$ 二分探索のコストから、上限として次の漸化式が得られます。

$T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{merge}}\left({\frac {3}{4}}n\right)+\Theta \left(\log(n)\right)$

解決策は $T_{\infty }^{\text{merge}}(n)=\Theta \left(\log(n)^{2}\right)$ つまり、プロセッサ数が無制限の理想的なマシンでは、それだけの時間がかかるということである。^{[ 7 ]}^{： 801-802}

注：このルーチンは安定していません。A $と$ $B$ を分割して同じ項目を分離すると、 $C$ ではそれらが混在してしまいます。また、 $A$ と $B$ を入れ替えると、同じ項目が両方の入力配列に分散している場合、順序が崩れてしまいます。そのため、このアルゴリズムをソートに使用すると、安定しないソート結果が生成されます。

2つのリストの並列マージ

また、2つのソート済みリストをマージする単一の処理内で並列性を導入するアルゴリズムも存在する。これらは、フィールドプログラマブルゲートアレイ（FPGA）、専用ソート回路、および単一命令複数データ（SIMD）命令を備えた最新のプロセッサで使用できる。

既存の並列アルゴリズムは、バイトニックソーターまたは奇偶マージソートのいずれかのマージ部分の修正に基づいています。^{[ 9 ]} 2018年、Saitoh M.らは、ハードウェアでの効率的なパイプライン処理を妨げていたマルチサイクルフィードバックデータパスの除去に焦点を当てたFPGA向けMMS ^{[ 10 ]}を発表しました。同じく2018年、Papaphilippou P.らは、ハードウェア利用率とパフォーマンスを向上させるために、必要なリソースを最小限に抑えたFLiMS ^{[ 9 ]を発表しました。} $\log _{2}(P)+1$ $P/2個$ の比較交換ユニットからなるパイプラインステージを、FPGAサイクルあたり $P個の要素の並列処理と統合する。$

言語サポート

一部のプログラミング言語では、ソートされたコレクションをマージするための組み込み機能またはライブラリ機能が提供されています。

C++

C ++の標準テンプレートライブラリには、2 つのソート済みイテレータ範囲をマージする関数std::mergeと、2 つの連続するソート済み範囲をインプレースでマージするstd::inplace_merge があります。さらに、std::list (リンクリスト) クラスには、別のリストを自身にマージする独自のmergeメソッドがあります。マージされる要素の型は、小なり演算子 ( < ) をサポートしているか、カスタム比較器を指定する必要があります。

C++17では、逐次実行、並列実行、並列非逐次実行など、さまざまな実行ポリシーが認められています。^{[ 11 ]}

Python

Pythonの標準ライブラリ（2.6以降）には、 heapqモジュールに複数のソート済みイテラブルを受け取り、それらを単一のイテレータにマージするmerge関数もあります。 ^[¹²^]

参考文献

1 2スキエナ、スティーブン（ 2010）。アルゴリズム設計マニュアル（第2 版）。Springer Science+Business Media。p . 123。ISBN 978-1-849-96720-4。
1 2 3 Kurt Mehlhorn ; Peter Sanders (2008).アルゴリズムとデータ構造: 基本ツールボックス. Springer. ISBN 978-3-540-77978-0。
↑カタヤイネン、ジルキ。パサネン、トミ。テウホラ、ユッカ (1996)。「実用的なインプレースマージソート」。ノルディック J. コンピューティング。3 (1 ) : 27–40。CiteSeerX 10.1.1.22.8523 。
↑ Kim, Pok-Son; Kutzner, Arne (2004). Stable Minimum Storage Merging by Symmetric Comparisons . European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723 . CiteSeerX 10.1.1.102.4612 . doi : 10.1007/978-3-540-30140-0_63 . ISBN 978-3-540-23025-0。
↑ Chandramouli, Badrish; Goldstein, Jonathan (2014).忍耐は美徳：現代のプロセッサにおけるマージとソートの再考。SIGMOD/PODS。
1 2 3 4 Greene, William A. (1993). k-way Merging and k-ary Sorts (PDF) . Proc. 31-st Annual ACM Southeast Conf. pp. 127–135 .
1 2コーメン、トーマスH.チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。アルゴリズム入門(第 3版)。 MIT プレスとマグロウヒル。ISBN 0-262-03384-4。
↑ Victor J. Duvanenko (2011)、「Parallel Merge」、Dr. Dobb's Journal
1 2 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: ソートのための高速軽量 2 方向マージ". IEEE Transactions on Computers : 1– 12. arXiv : 2112.05607 . doi : 10.1109/TC.2022.3146509 . hdl : 10044/1/95271 . S2CID 245669103 .
↑斎藤誠、エルサイード A.、チュウティエムヴァン、真下進、黄瀬健二 (2018 年 4 月) 「フィードバックデータパスのない高性能かつコスト効率の高いハードウェアマージソータ」2018 IEEE 第 26 回フィールドプログラマブルカスタムコンピューティングマシンに関する国際シンポジウム (FCCM) . pp. 197–204 . doi : 10.1109/FCCM.2018.00038 . ISBN 978-1-5386-5522-1. S2CID 52195866 .
↑ "std:merge" . cppreference.com. 2018-01-08 . 2018-04-28に取得.
↑ "heapq — ヒープキューアルゴリズム — Python 3.10.1 ドキュメント"。

さらに読む

ドナルド・クヌース著『コンピュータプログラミングの技法』第3巻：ソートと検索、第3版。アディソン・ウェスリー、1997年。ISBN 0-201-89685-0セクション 5.2.4「マージによるソート」の 158～160 ページ。セクション 5.3.2「最小比較マージ」、 197～207 ページ。

外部リンク

GitHubにソースコードがあるC#およびC++ GitHubでの並列および直列マージの高性能実装

[skiena-1] 1 2スキエナ、スティーブン（ 2010）。アルゴリズム設計マニュアル（第2 版）。Springer Science+Business Media。p . 123。ISBN 978-1-849-96720-4。

[toolbox-2] 1 2 3 Kurt Mehlhorn ; Peter Sanders (2008).アルゴリズムとデータ構造: 基本ツールボックス. Springer. ISBN 978-3-540-77978-0。

[3] カタヤイネン、ジルキ。パサネン、トミ。テウホラ、ユッカ (1996)。「実用的なインプレースマージソート」。ノルディック J. コンピューティング。3 (1 ) : 27–40。CiteSeerX 10.1.1.22.8523 。

[4] Kim, Pok-Son; Kutzner, Arne (2004). Stable Minimum Storage Merging by Symmetric Comparisons . European Symp. Algorithms. Lecture Notes in Computer Science. Vol. 3221. pp. 714–723 . CiteSeerX 10.1.1.102.4612 . doi : 10.1007/978-3-540-30140-0_63 . ISBN 978-3-540-23025-0。

[Chandramouli-5] Chandramouli, Badrish; Goldstein, Jonathan (2014).忍耐は美徳：現代のプロセッサにおけるマージとソートの再考。SIGMOD/PODS。

[greene-6] 1 2 3 4 Greene, William A. (1993). k-way Merging and k-ary Sorts (PDF) . Proc. 31-st Annual ACM Southeast Conf. pp. 127–135 .

[clrs-7] 1 2コーメン、トーマスH.チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。アルゴリズム入門(第 3版)。 MIT プレスとマグロウヒル。ISBN 0-262-03384-4。

[vjd-8] Victor J. Duvanenko (2011)、「Parallel Merge」、Dr. Dobb's Journal

[flimsj-9] 1 2 Papaphilippou, Philippos; Luk, Wayne; Brooks, Chris (2022). "FLiMS: ソートのための高速軽量 2 方向マージ". IEEE Transactions on Computers : 1– 12. arXiv : 2112.05607 . doi : 10.1109/TC.2022.3146509 . hdl : 10044/1/95271 . S2CID 245669103 .

[10] 斎藤誠、エルサイード A.、チュウティエムヴァン、真下進、黄瀬健二 (2018 年 4 月) 「フィードバックデータパスのない高性能かつコスト効率の高いハードウェアマージソータ」2018 IEEE 第 26 回フィールドプログラマブルカスタムコンピューティングマシンに関する国際シンポジウム (FCCM) . pp. 197–204 . doi : 10.1109/FCCM.2018.00038 . ISBN 978-1-5386-5522-1. S2CID 52195866 .

[11] "std:merge" . cppreference.com. 2018-01-08 . 2018-04-28に取得.

[12] "heapq — ヒープキューアルゴリズム — Python 3.10.1 ドキュメント"。

[ 1 ]

[ 2 ]

[

[

[ 5 ]

[

[

[

[ 9 ]

[ 10 ]

[ 11 ]

[

マージアルゴリズム

応用

2つのリストをマージする

Kウェイ合流

並列マージ

2つのリストの並列マージ

言語サポート

C++

Python

関連項目

参考文献

さらに読む

外部リンク

関連するトピック

ソート済み

アルゴリズム

サブルーチン

マージソートです