多相マージ

2025年10月20日

多相マージ

英語表記: Polyphase Merge

概要

多相マージは、大量のデータをソートする際に主記憶（メモリ）に収まりきらない状況、すなわち外部ソートの分野で利用される非常に効率的なマージ手法です。データを小さな塊（ラン）に分割した後、複数の外部記憶装置（磁気テープやディスク領域）を不均等に利用してマージを繰り返すことで、全体のI/O（入出力）回数を劇的に削減することを目的としています。このアルゴリズムは、特にマージのラウンド数を最小化するために、フィボナッチ数列などの特定の数学的シーケンスに基づいて初期のデータ配置を最適化する点が特徴的です。

詳細解説

多相マージは、「アルゴリズムと計算量」における「外部ソート」の効率化を目指して開発されました。外部ソートでは、データが主記憶に入らないため、ソート処理のボトルネックはCPUの計算速度ではなく、外部記憶装置へのアクセス（I/O）回数となります。いかにI/O回数を減らすかが、外部ソートの性能を決定づけるのです。

外部ソートにおける多相マージの役割

標準的な外部マージソート（例えば、バランスド・マージ）では、一般に$N$個の入力ファイルと$N$個の出力ファイルを交互に使い、均等にマージを行います。しかし、多相マージ（Polyphase Merge）では、この均等な利用をやめ、複数の入力ファイルから読み込み、たった一つの出力ファイルに書き出すという非対称なマージ戦略を採用します。これが「多相」（複数のフェーズを持つ、または複数の状態を持つ）と呼ばれる所以です。

動作原理：不均等な利用とフィボナッチ数列

多相マージの鍵となる構成要素は、初期のラン（ソート済みのデータブロック）の配置方法です。アルゴリズムは、使用する外部記憶装置の数（例えば、テープドライブの数 $k$）に基づき、特定の数列（$k=3$ ならフィボナッチ数列、より一般的には一般化フィボナッチ数列やトリボナッチ数列）の比率に従って、初期のランを配置します。

例えば、4台のテープドライブ（T1, T2, T3, T4）を使う場合を考えてみましょう。最初に、全てのランをT1, T2, T3に、特定の比率（例えば、フィボナッチ数列に基づく比率）で分散させます。そして、T1, T2, T3のランをマージしてT4に出力します。

ここで面白いのは、マージ後にT4に出力された新しいランの総数が、元のT1, T2, T3の中で最も少ないランの総数と同じになるように設計されている点です。つまり、マージ後、最も少ないランを持っていたテープ（仮にT3）は空になり、残りのT1とT2はランの数が減り、T4には新しいランが満たされます。

次のステップでは、空になったT3を新しい出力テープとして利用し、T1, T2, T4から読み込んでT3に出力します。このプロセスを繰り返すことで、マージのたびに必ず一つのテープが空き、それが次の出力先として使われるため、テープの切り替え（I/O装置の切り替え）が非常にスムーズかつ効率的に行われます。この巧妙な設計により、全体のラウンド数を最小限に抑え、結果としてI/O回数を大幅に削減できるのです。外部ソートにおいて、I/O回数はコストそのものですから、この効率性は非常に価値が高いと言えます。

具体例・活用シーン

多相マージは、特にコンピュータの主記憶容量がまだ小さかった時代、すなわち大規模なファイル処理が必須だったメインフレームや初期のデータベースシステムで絶大な力を発揮しました。現代においても、超巨大なデータセット（ビッグデータ処理）を扱う際のディスクベースのソート処理の基盤技術として知られています。

アナロジー：図書館の蔵書整理の物語

多相マージの仕組みを理解するために、ある図書館の蔵書整理を考えてみましょう。

あなたは図書館の司書で、数万冊のカード（データ）を整理する必要があります。カードはすでに小さな箱（ラン）にソートされていますが、すべてを一つの大きな目録（完全にソートされたファイル）にまとめる必要があります。使える作業台（外部記憶装置、例えばテープドライブ）は5つだけだとします。

通常の整理方法（バランスド・マージ）なら、2つの箱をまとめて新しい箱を作る作業を延々と繰り返すでしょう。しかし、多相マージの天才的な手法は違います。

まず、あなたはカードの箱を5つの作業台（A, B, C, D, E）に不均等に配置します。例えば、Aに21箱、Bに13箱、Cに8箱、Dに5箱、Eに0箱（空き台）と配置します。この「21, 13, 8, 5」という数字は、フィボナッチ数列に基づいた特別な比率です。

ステップ1： A, B, C, Dの4つの台から、最も少ない箱の数（Dの5箱）だけ同時にマージし、空き台Eに新しい5つの大きな箱を作成します。
マージ後、台Dは空になります。A, B, Cに残った箱はそれぞれ「21-5=16」「13-5=8」「8-5=3」となり、Eには5つの新しい箱ができます。

ステップ2： 次に、空になったDを出力台として使い、残りの3つの台（A, B, C, E）から、最も少ない箱の数（Cの3箱）だけマージし、Dに出力します。

このように、マージ処理のたびに必ず一つの台が空になり、それが次の出力台として利用されるため、常に効率的に作業を進めることができます。まるで、「玉突き」のように出力先が次々と変わっていく様子から、この名前がついたのかもしれませんね。この不均等な配置と交互利用の工夫こそが、外部ソートにおけるI/Oの無駄を極限まで減らす魔法なのです。

資格試験向けチェックポイント

多相マージは、特に応用情報技術者試験や高度試験において、外部ソートの効率化手法として出題されることがあります。基本情報技術者試験でも、ソートアルゴリズムの選択肢として知識が問われる可能性があります。

外部ソートの文脈: 多相マージは、主記憶（メモリ）に入りきらない大規模データ（ファイル）を扱う「外部ソート」の効率を高める技術であることを必ず覚えてください。内部ソート（クイックソート、ヒープソートなど）とは目的が異なります。
目的と効果: I/O回数（外部記憶装置へのアクセス回数）の削減が最大の目的です。これにより、ソート処理の全体時間を短縮できます。
重要なキーワード: 「不均等マージ」「フィボナッチ数列」「テープドライブの交互利用」がキーワードとなります。特に、マージ処理のたびに必ず一つの装置が空になり、次の出力先として使われるという動作原理を理解しておくと、選択肢問題で迷いません。
対比される用語: 「バランスド・マージ」と対比されることが多いです。バランスド・マージが均等に（例えば、半分の入力と半分の出力に分けて）装置を使うのに対し、多相マージは不均等に装置を使い、I/O効率を追求します。
計算量: 外部ソートの効率は通常、I/O回数で評価されます。多相マージは、特定の条件（特にテープドライブの数が多い場合）で他のマージ手法よりも少ないI/O回数で済む傾向があります。なぜ効率が良いのか、その仕組み（ランの配置最適化）を問われたら、フィボナッチ数列との関連を思い出しましょう。