松のページ　ソート

広告

twitter
Tweets by m_matsubara

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

ソート　（クイックソート・マージソートの改良アルゴリズムの提案）

概要

　クイックソート・マージソートの改良アルゴリズムを提案してみます。

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

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

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

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

　MatSortは一般的なマージソートと比較して作業領域を数分の１程度に縮小しても、元のマージソートよりも高速となる場合もある。作業領域サイズをソート対象の1/100まで圧縮しても、元のマージソートと同程度の速度を確保できた。

各アルゴリズムの解説

Many Pivot Sort

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

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

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

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

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

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

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

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

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

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

MasSort

MmSort.java
public static void MmSort.masSort(final T[] array, final int min, final int max, final Comparator comparator);
　一般的にマージソートのパフォーマンスは O(N Log₂ N)とされるが、同じくO(N Log₂ N)のパフォーマンスであらわされるクイックソートより何割か遅い。

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

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

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

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

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

MatSort

MmSort.java
public static void MmSort.matSort(final T[] array, final int min, final int max, final Comparator comparator, int workSize);
　マージソートは一般的に要素数(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, 1/100の作業領域サイズでベンチマークテストを行った。

　合わせて、Arrays.sort(Java 8標準のソート)、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)

　ハードウェア
　　システムの種類: x64-based PC
　　プロセッサ: Intel64 Family 6 Model 58 Stepping 9 GenuineIntel~3901 Mhz
　　 (Intel Core i7-3770)

乱数配列　結果は10回実行した平均 (秒)

配列サイズ	Many Pivot Sort	MasSort	MatSort (1/10)	MatSort (1/100)	Arrays.Sort	MergeSort	QuickSort	QuickSort (Median 3)
100	0.0002	0.0004	0.0002	0.0003	0.0002	0.0005	0.0001	0.0002
1000	0.0002	0.0009	0.0007	0.0007	0.0007	0.0007	0.0002	0.0002
10000	0.0065	0.0067	0.0068	0.0067	0.0067	0.0089	0.0054	0.0064
100000	0.0701	0.0317	0.0323	0.0328	0.0403	0.032	0.0561	0.0695
1000000	0.353	0.3601	0.4402	0.5055	0.4208	0.3956	0.3634	0.3609
10000000	3.2114	4.1122	4.3431	5.5516	4.8003	4.7976	3.7265	3.6786
100000000	43.2093	62.5433	58.9605	68.2513	72.0267	71.0432	50.9078	52.5126

昇順ソート済み配列　結果は10回実行した平均 (秒)

配列サイズ	Many Pivot Sort	MasSort	MatSort (1/10)	MatSort (1/100)	Arrays.Sort	MergeSort	QuickSort	QuickSort (Median 3)
100	0.0001	0.0002	0.0001	0.0002	0	0.0002	0.0001	0.0001
1000	0.0003	0.0001	0.0002	0.0001	0.0002	0.0002	0.0001	0.0002
10000	0.0036	0.0006	0.0003	0.0005	0.0004	0.0008	0.0013	0.0014
100000	0.0335	0.0012	0.0015	0.0008	0.0007	0.0053	0.0137	0.0338
1000000	0.0769	0.0104	0.0072	0.0103	0.0039	0.0183	0.077	0.0724
10000000	0.5563	0.1473	0.0967	0.0597	0.0257	0.1691	0.5399	0.5659
100000000	5.8978	1.2719	1.4033	0.9161	0.2129	1.8991	5.989	6.1085

降順ソート済み配列　結果は10回実行した平均 (秒)

配列サイズ	Many Pivot Sort	MasSort	MatSort (1/10)	MatSort (1/100)	Arrays.Sort	MergeSort	QuickSort	QuickSort (Median 3)
100	0	0.0001	0	0.0002	0.0002	0.0002	0.0001	0.0001
1000	0.0003	0.0004	0.0004	0.0002	0.0003	0.0006	0.0004	0.0003
10000	0.003	0.0051	0.0058	0.0054	0.002	0.0075	0.0031	0.0028
100000	0.0291	0.0201	0.0166	0.0114	0.0087	0.0245	0.0215	0.0293
1000000	0.0973	0.0838	0.1285	0.0754	0.0406	0.1433	0.0664	0.0807
10000000	0.5882	0.7441	0.7931	1.3792	0.2746	1.6692	0.5742	0.5746
100000000	6.2004	12.9923	7.9946	10.3531	3.2381	19.7838	6.0808	6.1278

全て同じキー値の配列　結果は10回実行した平均 (秒)

配列サイズ	Many Pivot Sort	MasSort	MatSort (1/10)	MatSort (1/100)	Arrays.Sort	MergeSort	QuickSort	QuickSort (Median 3)
100	0	0	0.0001	0.0002	0.0001	0.0001	0.0002	0.0002
1000	0.0003	0.0002	0.0001	0.0003	0	0.0002	0.0004	0.0002
10000	0.0065	0.0004	0.0008	0.0011	0.0002	0.0012	0.0069	0.007
100000	0.0265	0.0012	0.0041	0.0037	0.0007	0.0064	0.0218	0.0275
1000000	0.0775	0.011	0.0123	0.017	0.0041	0.0296	0.0677	0.0833
10000000	0.6097	0.147	0.1531	0.0994	0.027	0.3027	0.7859	0.7923
100000000	6.3859	1.2274	1.7602	1.378	0.2263	3.6606	9.0353	9.0929

ランダム配列（比較の回数）　結果は10回実行した平均 (回)

配列サイズ	Many Pivot Sort	MasSort	MatSort (1/10)	MatSort (1/100)	Arrays.Sort	MergeSort	QuickSort	QuickSort (Median 3)
100	683.1	526.8	591.8	887	532.2	526.8	671.7	683.1
1000	11069.8	8651.7	9203.1	11996.4	8675.1	8598.8	11435	11069.8
10000	143303.7	120650.6	125890.8	151684.5	120385.2	119265.6	159345	159190.9
100000	1795610.4	1525882.8	1599380.4	1851914.2	1534747.7	1525126.6	2041509.5	2022463.4
1000000	21560342.9	18622899.5	19189763.2	21928149.1	18640503.1	18583279.2	25409203.5	25019783.8
10000000	247390458.3	220326722	225537341.8	251229532.4	220247288.9	218943701.3	298758227.9	300010878.4
100000000	2820894947	2522494442.6	2596358506	2848689510.7	2530496048.5	2521685999.5	3436000610.8	3427142947.5

ソースファイル

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

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

各々のファイルについて
src/mmsort/ManyPivotSort.java 「Many Pivot Sort」とコムソート・クイックソート（比較用）の実装
src/mmsort/MmSort.java 「MasSort」、「MatSort」及び、挿入ソート・挿入ソート（二分探索版）・マージソート（比較用）の実装
src/mmsort/SortTest.java 各種ソートのベンチマークプログラム
src/test.bat ベンチマーク起動用バッチファイル(Windows 用)
src/testAll.bat ベンチマーク起動用バッチファイル(Windows 用)
LICENSE.txt ライセンスファイル（MITライセンス）
testAll.txt ベンチマーク結果

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

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

コンタクト

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

aaa

ソート （クイックソート・マージソートの改良アルゴリズムの提案）

概要