Many Pivot Sort, MasSort, MatSort（クイックソート・マージソートの改良アルゴリズムの提案）

twitter

Tweets by m_matsubara

GitHub

m-matsubara

※A5:SQL Mk-2はGitHubのプライベートリポジトリで開発されているためソースコードを参照することはできません。

Many Pivot Sort, MasSort, MatSort
（最速のソートを目指して…クイックソート・マージソートの改善）

概要

Many Pivot Sort クイックソートのピボット値選択方法改善アルゴリズム

MasSort メモリの操作回数低減を狙ったマージソートの改善アルゴリズム

MatSort 作業領域のメモリ使用料量削減を狙ったマージソートの改善アルゴリズム（MasSort等、他のマージソート系アルゴリズムを内部的に併用する）

　Many Pivot Sort, MasSortはクイックソート、マージソートの改善版でそれぞれ、元のアルゴリズムから10-20%程度高速化している。

　MatSortは作業領域をソート対象の1/10程度に縮小しても元のマージソートよりも高速であり、ランダム配列においてはベースとなるMasSortに近い結果が得られた。

※現在この文書の内容は Version 2.0.1 となっています。古いバージョンの文書については以下を参照してください。

Version 1.0

各アルゴリズムの解説

Many Pivot Sort

ManyPivotSort.java
　よく使われる高速なソートアルゴリズムとしてクイックソートがある。しかしクイックソートには明確な弱点として、ピボット値（基準値）の選択を誤るとパフォーマンスが劇的に悪化するという問題がある。期待値としてのクイックソートの計算量はO(N log₂ N)であるが、最悪計算量はO(N²)である。

　ピボット値を選択する技法としてよく使われるものは、配列の中央位置を選択する技法、配列から３ヶ所の値を取り出し中央値を選択する技法、配列のランダムな位置から値を選択する技法がある。

　ここでは、これらに代わって効率よく集団の中央値に近い値を選択可能なアルゴリズムを考案する。

アルゴリズムの概要は以下の通り
１．事前にソート対象からM個(数十から数百程度、2の乗数-1が無駄がない)のピボット候補を選択する。
　ピボット候補の選択方法は、ソート対象の配列から等間隔でM個採取するなど行う。
２．M個のピボット候補を少ない数で効率が良いアルゴリズムでソートを行う。
　（たとえばコムソート、安定でなくともよい）
３．ピボット候補配列の中央の値(M/2番目)をピボット値としてソート対象をクイックソートする。
　クイックソート中での再帰的なクイックソートの呼び出しは、「４．」，「５．」を参照のこと。
４．ピボット値以下の集団に対しては、ピボット候補のうち、今回選択したピボット値よりも小さいピボット候補群を新たなピボット候補としてクイックソートを行う。
　この時、ピボット候補の数が一定数未満（たとえば３未満）であった場合は、１に戻り、ピボット候補を再構築する。
５．ピボット値以上の集団に対しては、ピボット候補のうち、今回選択したピボット値よりも大きいピボット候補を新たなピボット候補群としてクイックソートを行う。
　この時、ピボット候補が一定数未満（たとえば３未満）であった場合は、１に戻り、ピボット候補を再構築する。

　つまり、このアルゴリズムにおいては事前に数十個以上のピボット候補を選択しソートしておくことで、よりソート対象の中央値に近いピボット値を得られることを期待する。

　より中央に近いピボット値が得られれば、ピボット値以下・ピボット値以上の集団への分割がより均等に行われ、ひいては再帰での呼び出しの深さが低くなり、より期待値に近い計算量を達成することが可能となる。

　数十個以上のピボット候補を選択することは、小さくないオーバーヘッドが必要だが、一度ピボット候補を選択すれば、ピボット候補の前半・後半を再度ピボット候補とみなして再利用することで、数段分の再帰処理についてはオーバーヘッド無しに、より中央値に近いピボット値を選択することができる。

　問題点として、このアルゴリズムは一度に大量のピボット候補を選択することから最悪計算量に陥りにくいが、このアルゴリズムを前提として、最悪に近い計算量になるように配列を作る元は可能と思う。

　また、ピボット候補の配列を別に確保することから、一般的なクイックソートアルゴリズムよりも多くの作業メモリを必要とする。これは外部ソートに分類されるかもしれない。

　計算量は通常のクイックソートと同様で期待値としては O(N log₂ N)であり、最悪計算量も変わらず、O(N²⁾ となるが、実質的な計算量は一般的なクイックソートよりも期待値に近くなることが期待できる。

MasSort

MasSort.java
　一般的にマージソートのパフォーマンスは O(N Log₂ N)とされるが、同じくO(N Log₂ N)のパフォーマンスであらわされるクイックソートより何割か遅い。

　これは、クイックソートと比べてメモリ転送回数が多いためではないかと考えた。このためメモリのデータ転送回数を少なくするための改善を考えた。

　一般的なマージソートはソート対象を2つに分け、そのたびにマージ操作でメモリ転送が発生するが、新しいMasSortにおいてはソート対象をより多く(たとえば32個ほど)のブロックに分けてマージを行うことでメモリ転送回数を数分の１程度に減らす。

　具体的には作業領域にいったんコピーし、分割した各々のブロックをソート済みキューとみなし、キュー自身を先頭要素の値でソートすることで最小値を取り出していく。

　問題点としては、一般的なマージソート実装はソート対象の半分の作業領域を必要とするが、この実装ではソート対象と同サイズの作業領域を必要とする。論理的には最後のブロックは作業領域に転送する必要はないが、制御が複雑になるため、最後のブロックも含めてすべて作業領域に転送している。

　計算量は通常のマージソートと同様 O(N log₂ N)のままであるが、後述のベンチマークでは一般的なマージソートより良い結果が得られた。

MatSort

MatSort.java
　マージソートは一般的に要素数(N)の半分のサイズの作業領域を必要とするという制約があるが、MatSortでは作業領域のサイズは任意に指定できる。これは時間と空間のトレードオフとなる。

　一般的なマージソートアルゴリズムは以下の手順によって実行される。

１．配列の前半分に対して事前にマージソートを使いソートする。
２．配列の後ろ半分に対して事前にマージソートを使いソートする。
３．配列の前半分を作業領域にコピーする。
４．作業領域（配列の前半分のコピー）と配列の後ろ半分を使ってマージ作業を行う。
　　（未処理の作業領域の先頭要素と後ろ半分の先頭要素を比較し、どちらか小さい方を配列のソート済み領域にコピーしていく。）

　上述のように前半分のコピーを保持するために作業領域が必要となり、このために要素数(N)の半分のサイズの作業領域が必要となる。

　この時注意が必要なのは、３, ４で示されるマージ作業は要素数(N)の半分が必要なのではなく、あくまでも「前半分」の領域サイズのみ必要となることである。

　このためMatSortでは、前半分のサイズを意図的に小さくすることで作業領域を節約する。これの実現のために、全体を数個～数十個程度のブロックに分割し、各々のブロックをソートする。この後、後ろのブロックから随時マージ作業を行っていく。具体的な手順は以下のようになる。
１．作業領域サイズごとに配列を分割する。これをブロックと呼ぶ。
２．すべてのブロックに対してMasSortを行う。
３．最後のブロックとその一つ前のブロックを作業領域を使いながらマージする。これを新しい最後の(大きな)ブロックとし、全体が１つのブロックになるまでマージを繰り返す。

　また、マージを繰り返すにつれて最後のブロックは大きくなるため、マージ時には、後半のブロックから値が取り出される確率が前半のブロックから取り出される確率よりもかなり高くなる。つまり後半のブロックからは連続して値が取り出される可能性が高くなる。このため、前方から範囲を２倍に拡大しつつ検索範囲を確定し、その後２分探索を行うことで高速化を図っている。これはTimSortのギャロッピングモードと同様の動作となる。

　問題点としては、マルチスレッドによる並列演算にあまり適さないということがある。技術的には各ブロックは独立して事前にソート可能であるが、そのためにはスレッド数分の作業領域を必要とする。このことは MatSort の目的である作業領域の削減という目的と相反する。

　計算量（作業手数の概算・近似値）は以下のようになる。
　N = 全体サイズ
　M = ワークメモリサイズ
　L = N / M … 全体サイズとワークメモリのサイズの比

　計算量 = L (N / L log₂ (N / L)) + (N / 2)(L - 1)
　 = (N log₂ (N / L)) + N L / 2 - (N / 2)
　 = (N log₂ (N / L)) + N L / 2 - (N / 2)

　各々、+演算子の左辺(赤)は、各ブロック毎にソート(L個)する計算量で、右辺(青)はL個のブロックを１つにマージするための計算量となる。
　ここで、L=1の場合（全体サイズ=ワークメモリサイズ）右辺は0となり、O表記では、O(N log₂ N)となる。
　L=Nの場合（ワークメモリサイズ=1）左辺は (N log₂ 1)となり、右辺は(N² / 2 - (N / 2))に変形できるから、O表記ではO(N²)となる。
　つまり、Lの値に従い計算量はO(N log₂ N)からO(N²)まで連続的に変化する。
　また、Lが固定であるなら、右辺はO(N)としかならないから、全体では O(N log₂ N) の作業量となる。　後述のベンチマークでは、L=10程度なら、O(N log₂ N)に近い実測値が得られた。

ベンチマーク

　以下に今回作成した、Many Pivot Sort及び、MasSort, MatSortのベンチマーク結果を掲載する。

　Matソートに関しては作業領域サイズを任意に指定できるため、配列サイズの1/10の作業領域サイズでベンチマークテストを行った。

　合わせて、Arrays.sort(Java 8標準のソート・TimSort)、Merge Sort(標準的なマージソート)、Quick Sort(標準的なクイックソート)、Quicksort(Median 3)(ピボット値の選択が3つのメディアンになっている標準的なクイックソート)についてもベンチマーク結果を掲載する。

　実行環境は以下の通り
　Java バージョン
　　java version "1.8.0_40"
　　Java(TM) SE Runtime Environment (build 1.8.0_40-b25)
　　Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)

ランダムデータ (時間：10回実行した平均（秒）)

アルゴリズム	100	1000	10000	100000	1000000	10000000	100000000
Many Pivot Sort	0.002	0.001	0.007	0.044	0.296	3.117	42.593
Many Pivot Sort (3 Way)	0.000	0.001	0.004	0.055	0.372	3.288	43.542
Quick Sort (Median of 3)	0.000	0.000	0.003	0.022	0.294	3.046	44.227
Quick Sort	0.000	0.000	0.006	0.071	0.395	3.585	49.723
MasSort	0.000	0.001	0.010	0.029	0.369	4.010	57.535
MatSort	0.002	0.001	0.007	0.032	0.461	4.610	59.438
Arrays.Sort	0.001	0.000	0.006	0.041	0.405	4.547	69.795
Merge Sort	0.000	0.001	0.008	0.030	0.402	4.786	72.191
Improved Merge Sort	0.000	0.000	0.007	0.028	0.403	4.587	72.967
In-place Merge Sort	0.000	0.001	0.008	0.067	0.855	12.746	222.223

昇順ソート済みデータ (時間：10回実行した平均（秒）)

アルゴリズム	10000	100000	1000000	10000000	100000000
Arrays.Sort	0.000	0.001	0.004	0.025	0.205
MasSort	0.001	0.001	0.010	0.136	0.931
MatSort	0.000	0.002	0.008	0.109	1.483
Merge Sort	0.001	0.004	0.020	0.163	1.825
In-place Merge Sort	0.001	0.003	0.017	0.180	1.939
Quick Sort (Median of 3)	0.001	0.007	0.034	0.360	4.082
Many Pivot Sort	0.003	0.014	0.058	0.395	4.530
Many Pivot Sort (3 Way)	0.002	0.016	0.116	0.565	4.830
Improved Merge Sort	0.001	0.008	0.044	0.452	4.911
Quick Sort	0.001	0.040	0.069	0.506	5.385

降順ソート済みデータ (時間：10回実行した平均（秒）)

アルゴリズム	1000	10000	100000	1000000	10000000	100000000
Arrays.Sort	0.000	0.002	0.009	0.039	0.262	3.209
Quick Sort (Median of 3)	0.000	0.002	0.011	0.040	0.420	4.604
Many Pivot Sort (3 Way)	0.001	0.002	0.015	0.144	0.560	5.087
Many Pivot Sort	0.000	0.002	0.017	0.069	0.429	5.634
Quick Sort	0.000	0.002	0.019	0.067	0.556	5.979
MatSort	0.001	0.006	0.022	0.142	0.814	8.013
MasSort	0.001	0.003	0.014	0.085	0.770	10.533
Improved Merge Sort	0.001	0.007	0.019	0.119	1.685	17.254
Merge Sort	0.001	0.007	0.025	0.150	1.722	19.696
In-place Merge Sort	0.001	0.006	0.036	0.519	11.484	206.989

全て同値キーデータ (時間：10回実行した平均（秒）)

アルゴリズム	100	1000	10000	100000	1000000	10000000	100000000
Many Pivot Sort	0.002	0.001	0.007	0.044	0.296	3.117	42.593
Many Pivot Sort (3 Way)	0.000	0.001	0.004	0.055	0.372	3.288	43.542
Quick Sort (Median of 3)	0.000	0.000	0.003	0.022	0.294	3.046	44.227
Quick Sort	0.000	0.000	0.006	0.071	0.395	3.585	49.723
MasSort	0.000	0.001	0.010	0.029	0.369	4.010	57.535
MatSort	0.002	0.001	0.007	0.032	0.461	4.610	59.438
Arrays.Sort	0.001	0.000	0.006	0.041	0.405	4.547	69.795
Merge Sort	0.000	0.001	0.008	0.030	0.402	4.786	72.191
Improved Merge Sort	0.000	0.000	0.007	0.028	0.403	4.587	72.967
In-place Merge Sort	0.000	0.001	0.008	0.067	0.855	12.746	222.223

ランダムデータ (比較回数：10回実行した平均（回）)

アルゴリズム	100	1000	10000	100000	1000000	10000000	100000000
Improved Merge Sort	527	8592	119203	1524616	18575088	218878166	2521161713
Merge Sort	527	8599	119266	1525127	18583279	218943701	2521686000
MasSort	527	8652	120651	1525883	18622900	220326722	2522494443
Arrays.Sort	532	8675	120385	1534748	18640503	220247289	2530496049
MatSort	592	9203	125891	1599380	19189763	225537342	2596358506
Many Pivot Sort (3 Way)	508	8941	123219	1585771	19364306	228891871	2633723073
Many Pivot Sort	763	12191	153060	1885352	22408601	256900851	2914248341
Quick Sort (Median of 3)	763	12191	160718	2021684	24240042	284961051	3266912797
Quick Sort	672	11435	159345	2041510	25409204	298758228	3436000611
In-place Merge Sort	527	11186	171573	2250584	27880454	334072027	3880765565

ソースファイル

　Javaで実装されたソースファイルを以下で公開しています。

GitHub リポジトリ
https://github.com/m-matsubara/sort

各々のファイルについて
src/mmsort/ManyPivotSort.java Many Pivot Sort のリファレンス実装
src/mmsort/ManyPivotSort.java Many Pivot Sort の3 Way partition版
src/mmsort/MasSort.java MasSort のリファレンス実装
src/mmsort/MatSort.java MatSort のリファレンス実装
src/mmsort/BinInsertionSort.java 二分挿入ソート
src/mmsort/CombSort.java コムソート
src/mmsort/ImprovedMergeSort.java 改良版ソート(比較用)
src/mmsort/InplaceMergeSort.java インプレース・マージソート(比較用)
src/mmsort/InsertionSort.java 挿入ソート(比較用)
src/mmsort/ManyPivotSort3W.java Many Pivot Sort (3 way partition版・まだそんなに速くない)
src/mmsort/MergeSort.java マージソート(比較用)
src/mmsort/QuickSort.java クイックソート(比較用)
src/mmsort/QuickSortM3.java クイックソート（３つのメディアン・比較用）
src/mmsort/Simple_ManyPivotSort.java Many Pivot Sort (シンプルな実装版)
src/mmsort/Simple_MasSort.java MasSort (シンプルな実装版)
src/mmsort/Simple_MatSort.java MatSort (シンプルな実装版)
src/mmsort/SortTest.java 各種ソートのベンチマークプログラム
src/mmsort/ISortAlgorithm.java 各種ソートのベンチマークプログラムで使うインターフェース
src/test.bat ベンチマーク起動用バッチファイル(Windows 用)
src/testAll.bat ベンチマーク起動用バッチファイル(Windows 用)
LICENSE.txt ライセンスファイル（MITライセンス）
testAll.txt ベンチマーク結果

このコンテンツの扱いについて（著作権・ライセンス・アルゴリズムの利用について）

　このコンテンツの目的は著作物の配布ではなく、アルゴリズムの提案です。ここで提案するアルゴリズム自体は特許や著作権に左右されず改変も含めて自由に再実装（他の言語への移植を含む）をしていただいて構いません。またJavaによる実装が提供されますが、この実装(著作物)はMITライセンスに基づき商用を含め自由にご利用いただけます。

コンタクト

質問・要望・不具合報告などあればお待ちしております。

Many Pivot Sort, MasSort, MatSort（最速のソートを目指して…クイックソート・マージソートの改善）

概要