多相マージソート

ポリフェーズ マージ ソートは、ボトムアップマージ ソートのバリエーションであり、サブリスト (ラン) の初期不均等な分散を使用してリストをソートします。主に外部ソートに使用され、外部作業ファイル (テープ ドライブやハード ドライブ上のファイルなど) が 8 個未満の場合は、通常のマージ ソートよりも効率的です。ポリフェーズ マージ ソートは安定したソートではありません。

マージソートでは、データセットのレコードをソートされたレコードの実行に分割し、ソートされた実行をより大きなソートされた実行に繰り返しマージして、ソートされたデータセットの実行だけが残るまで続けます。

4 つの作業ファイルを使用した「バランスのとれた」マージ ソートでは、それらの作業ファイルを入力ファイルのペアと出力ファイルのペアとして整理します。データセットは、ソートされた実行として、または最も単純なケースでは、サイズ 1 のソートされた実行と見なすことができる単一のレコードとして、2 つの作業ファイル間で均等に分散されます。データセット全体が 2 つの作業ファイルに転送されると、それらの 2 つの作業ファイルが最初のマージ反復の入力ファイルになります。各マージ反復では、2 つの入力作業ファイルからの実行がマージされ、マージされた出力が 2 つの出力ファイル間で交互に出力され、マージされた実行が再び 2 つの出力ファイル間で均等に分散されます (最後のマージ反復まで)。2 つの入力ファイルからのすべての実行がマージされて出力されると、出力ファイルが次のマージ反復で入力ファイルになり、その逆も同様です。実行回数は、64、32、16、8、4、2、1 のように、反復ごとに係数 2 ずつ減少します。最後のマージ反復では、2 つの入力ファイルにはそれぞれ 1 つのソート済み実行 (データセットの 1/2) のみがあり、マージされた結果は、出力ファイルの 1 つに 1 つのソート済み実行 (ソート済みデータセット) になります。これについては、マージ ソート § テープ ドライブでの使用でも説明されています。

作業ファイルが 3 つしかない場合、バランス マージ ソートは、2 つの作業ファイルからソートされた実行を 1 つの作業ファイルにマージし、その実行を 2 つの出力ファイル間で均等に分配します。マージ反復では実行回数が 2 分の 1 に減りますが、再分配反復では実行回数は減りません (係数は 1)。各反復では、実行回数が平均係数√ 2 ≈ 1.41 に減ると考えられます。作業ファイルが 5 つある場合、パターンは 3 方向マージと 2 方向マージを交互に繰り返し、平均係数は√ 6 ≈ 2.45 になります。

一般に、作業ファイルの数N が偶数の場合、バランスマージソートの各反復で実行回数がN /2 倍に減少しますが、作業ファイルの数Nが奇数の場合、各反復で実行回数が平均で√ ( N ² −1)/4 = √ N ² −1 /2倍に減少します。

N < 8 の作業ファイルの場合、ポリフェーズ マージ ソートでは、ソートされた実行をN −1 個の作業ファイル間で不均等に分散することによって、実行回数の削減係数を効果的に高めることができます (次のセクションで説明)。各反復では、 N −1 個の作業ファイルからの実行を1 つの出力作業ファイルにマージします。N −1個の作業ファイルのいずれかの末尾に到達すると、それが新しい出力ファイルになり、出力ファイルだったものがN −1 個の作業入力ファイルの 1 つになり、ポリフェーズ マージ ソートの新しい反復が開始されます。各反復では、データセットの一部 (約 1/2 ～ 3/4) のみがマージされますが、最後の反復ではデータセット全体が 1 つのソートされた実行にマージされます。最初の分散は、一度に 1 つの入力作業ファイルのみが空になるように設定されますが、最後のマージ反復では、N −1 個の入力作業ファイルからのN −1 個の単一実行 (サイズはさまざま、次で説明) が1 つの出力ファイルにマージされ、結果として単一のソートされた実行、つまりソートされたデータセットが生成されます。

各ポリフェーズ反復では、実行の合計数は、高次の数列の逆フィボナッチ数列に似たパターンに従います。4 つのファイルと 57 の実行で構成されるデータセットの場合、各反復での合計実行数は 57、31、17、9、5、3、1 になります。^{[1] [2]}最後の反復を除いて、実行数の削減係数は 2 より少し小さく、57/31、31/17、17/9、9/5、5/3、3/1 で、4 ファイルの場合約 1.84 ですが、最後の反復を除く各反復ではデータセットの約 65% を処理しながら実行数が削減されたため、中間の反復中に処理されるデータセットあたりの実行数削減係数は約 1.84 / 0.65 = 2.83 になります。それぞれ 1 レコードの実行が 57 回行われたデータセットの場合、最初の分散の後、多相マージ ソートではデータセットのソートに必要な 6 回の反復中に 232 レコードが移動され、全体的な削減係数は 2.70 になります (詳細は後述します)。

最初の多相反復の後、出力ファイルにはN −1 個の元の実行をマージした結果が含まれるようになりましたが、残りのN −2 個の入力作業ファイルにはまだ残りの元の実行が含まれているため、2 番目のマージ反復では、サイズが ( N −1) + ( N −2) = (2 N − 3) 個の元の実行の実行が生成されます。3 番目の反復では、サイズが (4 N − 7) 個の元の実行の実行が生成されます。4 つのファイルでは、最初の反復でサイズが 3 個の元の実行の実行が作成され、2 番目の反復では 5 個の元の実行の実行が作成され、3 番目の反復では 9 個の元の実行が作成され、フィボナッチのようなパターン (1、3、5、9、17、31、57、...) に従って実行されます。したがって、実行サイズの増加は、実行数の減少と同じパターンに逆に従います。 4 つのファイルと 1 レコードずつの 57 回のランの例では、最後の反復でサイズが 31、17、9 の 3 つのランがマージされ、サイズが 31+17+9 = 57 レコードの単一のソート済みラン、つまりソート済みデータセットが生成されます。4 つのファイルと 31 レコードのラン数とラン サイズの例は、^{[3]の表 4.3 にあります。}

ポリフェーズ マージを終了条件から逆順に見ていくのが最も簡単です。各反復の開始時には、2 つの入力ファイルと 1 つの出力ファイルがあります。反復の終了時には、1 つの入力ファイルが完全に消費され、次の反復の出力ファイルになります。現在の出力ファイルは、次の反復の入力ファイルになります。残りのファイル (3 つのファイルの場合は 1 つだけ) は部分的にしか消費されておらず、残りの実行が次の反復の入力になります。

ファイル 1 が空になり、新しい出力ファイルになりました。各入力テープには 1 つの実行が残っており、それらの実行を結合すると、ソートされたファイルが作成されます。

ファイル 1 (出力): <1 実行> * (ソートされたファイル)
ファイル 2 (in ): ... | <1 実行> * --> ... <1 実行> | * (消費済み)
ファイル 3 (in ): | <1 実行> * <1 実行> | * (消費済み)

...すでに読み取られた可能性のある実行
| ファイルの読み取りポインタを示します
* ファイルの終わりを示します

前の反復に戻って、1 と 2 から読み取りを行っていました。ファイル 1 が空になる前に、1 と 2 から 1 回の実行がマージされます。ファイル 2 は完全には消費されていないことに注意してください。最後のマージ (上記) と一致するように、1 回の実行が残っています。

ファイル 1 (in): ... | <1 実行> * ... <1 実行> | *
ファイル 2 (in ): | <2 実行> * --> <1 実行> | <1 実行> *
ファイル3（出力）: <1 実行> *

もう 1 回反復を戻すと、ファイル 3 が空になる前に、1 と 3 から 2 回の実行がマージされます。

ファイル 1 (in ): | <3 実行> ... <2 実行> | <1 実行> *
ファイル2（出力）: --> <2 実行> *
ファイル 3 (in): ... | <2 実行> * <2 実行> | *

もう 1 回反復を戻すと、ファイル 2 が空になる前に、2 と 3 から 3 回の実行がマージされます。

ファイル1（出力）: <3 実行> *
ファイル 2 (in ): ... | <3 実行> * --> ... <3 実行> | *
ファイル 3 (in ): | <5 実行> * <3 実行> | <2 実行> *

もう 1 回反復を戻すと、ファイル 1 が空になる前に、1 と 2 から 5 回の実行がマージされます。

ファイル 1 (in): ... | <5 実行> * ... <5 実行> | *
ファイル 2 (in ): | <8 実行> * --> <5 実行> | <3 実行> *
ファイル3（出力）: <5 実行> *

完璧な 3 つのファイルの場合、逆方向にマージされた実行回数は 1、1、2、3、5、... となり、フィボナッチ数列になります。3 つ以上のファイルの場合のシーケンスは少し複雑です。4 つのファイルの場合、最終状態から逆方向に実行回数パターンは {1,0,0,0}、{0,1,1,1}、{1,0,2,2}、{3,2,0,4}、{7,6,4,0}、{0,13,11,7}、{13,0,24,20}、... となります。

すべてが最適に機能するには、最後のマージ フェーズで各入力ファイルに対して 1 回だけ実行する必要があります。入力ファイルに複数の実行がある場合は、別のフェーズが必要になります。したがって、ポリフェーズ マージ ソートでは、入力データの実行を初期出力ファイルに初期配分する方法について適切に処理する必要があります。たとえば、実行が 13 個ある入力ファイルでは、ファイル 1 に 5 個、ファイル 2 に 8 個が書き込まれます。

実際には、入力ファイルには、完全な分布に必要な実行の正確な数はありません。これに対処する方法の 1 つは、実際の分布に架空の「ダミー実行」を追加して、理想的な実行分布をシミュレートすることです。^[1]ダミー実行は、レコードのない実行のように動作します。1 つ以上のダミー実行を 1 つ以上の実際の実行とマージすると、実際の実行がマージされるだけであり、1 つ以上のダミー実行を実際の実行なしでマージすると、1 つのダミー実行になります。別のアプローチは、マージ操作中に必要に応じてダミー実行をエミュレートすることです。^[4]

「最適な」分散アルゴリズムでは、実行回数を事前に知っている必要があります。そうでない場合、実行回数が事前にわからない一般的なケースでは、「最適に近い」分散アルゴリズムが使用されます。一部の分散アルゴリズムには、実行の並べ替えが含まれます。^[5]実行回数が事前にわかっている場合は、マージ フェーズを開始する前に部分的な分散のみが必要です。たとえば、 File_1 でn実行から始まる 3 つのファイルのケースを考えます。Fi = F _{i −1} + F _{i −2 を}i番目のフィボナッチ数として定義します。n = F i の場合は、Fi _i −2_実行を File_2 に移動し、_{File_1に}はF _{i −1実行が残ります。}これは完全な実行分散です。Fi < n < F i +1 の場合は_、 n − F i_実行をFile_2 に移動し、 Fi +1 ₋ n実行_をFile_3に移動します_。最初のマージ反復では、File_1 と File_2 からのn − F _i実行がマージされ、 n − F _{i の}マージされた実行が、すでに File_3 に移動されているF _{i +1} − n実行に追加されます。File_1 にはF _{i −2実行が残り、File_2 は空になり、File_3 には}F _{i −1}実行が残ります。この場合も、実行の完全な分散になります。4 つ以上のファイルの場合、計算はより複雑になりますが、概念は同じです。

初期分散後、4 つのファイルを使用したバランス マージ ソートでは、データセット全体の 4 回の反復で 16 個の単一レコード実行をソートし、初期分散後のデータセットをソートするために合計 64 個のレコードを移動します。4 つのファイルを使用したポリフェーズ マージ ソートでは、4 回の反復で 17 個の単一レコード実行をソートしますが、最後の反復を除く各反復ではデータセットの一部のみが移動されるため、初期分散後のデータセットをソートするために移動するレコードは合計 48 個のみです。この場合、バランス マージ ソート係数は 2.0 で、ポリフェーズ全体の係数は ≈2.73 です。

削減係数がソート パフォーマンスにどのように関係するかを説明する削減係数の式は次のとおりです。

削減係数 = exp(実行回数*log(実行回数)/実行移動回数)
run_move_count = 実行回数 * log(実行回数)/log(削減係数)
run_move_count = 実行回数 * log_reduction_factor(実行回数)

上記の例に実行移動カウント方程式を使用すると、次のようになります。

• バランスマージソート → ⁠ ⁠${\displaystyle 16\times \log _{2}(16)=64}$、
• 多相マージソート → ⁠ ⁠${\displaystyle 17\times \log _{2.73}(17)=48}$ .

これは、数百万件のレコードの実際のソートに基づいて、ファイル数別にリストされた多相およびバランスのとれたマージソートの有効な削減係数の表です。この表は、多相マージソート.pdf の図 3 および図 4 に示されている、移動されたデータセットごとの削減係数の表とほぼ一致しています。

# ファイル
| 反復ごとのデータの平均割合
| | 理想的なサイズのデータ​​に対する多相削減係数
| | | 理想的なサイズのデータ​​に対するバランスのとれた削減係数
| | | |
3 .73 1.94 1.41 (平方2)
4 .63 2.68 2.00
5 .58 3.20 2.45 (平方6)
6 .56 3.56 3.00
7 .55 3.80 3.46 (平方12)
8 .54 3.95 4.00
9 .53 4.07 4.47 (平方20)
10 .53 4.15 5.00
11 .53 4.22 5.48 (平方30)
12 .53 4.28 6.00
32 .53 4.87 16.00

一般的に、ファイル数が8未満の場合は多相マージソートの方がバランスマージソートよりも優れていますが、ファイル数が8以上になるとバランスマージソートの方が優れ始めます。^{[6] [7]}

• ブラッドリー、ジェームズ（1982）、ファイルとデータベース技術、ホルト、ライナーハート、ウィンストン、ISBN 0-03-058673-9
• レイノルズ、サミュエル W. (1961 年 8 月)、「一般化された多相マージ アルゴリズム」、Communications of the ACM、4 (8)、ニューヨーク、NY: ACM: 347–349、doi : 10.1145/366678.366689、S2CID  28416100
• セジウィック、ロバート（1983）、アルゴリズム、アディソン・ウェズレー、pp. 163-165、ISBN 0-201-06672-6