広告






twitter


掲示板

FeedWind
      

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 log2 N)であるが、最悪計算量はO(N2)である。

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

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

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

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

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

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

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

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

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

    MasSort

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

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

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

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

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

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

    MatSort

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

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

    1.配列の前半分に対して事前にマージソートを使いソートする。
    2.配列の後ろ半分に対して事前にマージソートを使いソートする。
    3.配列の前半分を作業領域にコピーする。
    4.作業領域(配列の前半分のコピー)と配列の後ろ半分を使ってマージ作業を行う。
      (未処理の作業領域の先頭要素と後ろ半分の先頭要素を比較し、どちらか小さい方を配列のソート済み領域にコピーしていく。)

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

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

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

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

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

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

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

     各々、+演算子の左辺()は、各ブロック毎にソート(L個)する計算量で、右辺()はL個のブロックを1つにマージするための計算量となる。
     ここで、L=1の場合(全体サイズ=ワークメモリサイズ)右辺は0となり、O表記では、O(N log2 N)となる。
     L=Nの場合(ワークメモリサイズ=1)左辺は (N log2 1)となり、右辺は(N2 / 2 - (N / 2))に変形できるから、O表記ではO(N2)となる。
     つまり、Lの値に従い計算量はO(N log2 N)からO(N2)まで連続的に変化する。
     また、Lが固定であるなら、右辺はO(N)としかならないから、全体では O(N log2 N) の作業量となる。  後述のベンチマークでは、L=10程度なら、O(N log2 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回実行した平均(秒))
    アルゴリズム100100010000100000100000010000000100000000
    Many Pivot Sort0.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 Sort0.000 0.000 0.006 0.071 0.395 3.585 49.723
    MasSort0.000 0.001 0.010 0.029 0.369 4.010 57.535
    MatSort0.002 0.001 0.007 0.032 0.461 4.610 59.438
    Arrays.Sort0.001 0.000 0.006 0.041 0.405 4.547 69.795
    Merge Sort0.000 0.001 0.008 0.030 0.402 4.786 72.191
    Improved Merge Sort0.000 0.000 0.007 0.028 0.403 4.587 72.967
    In-place Merge Sort0.000 0.001 0.008 0.067 0.855 12.746 222.223


    昇順ソート済みデータ (時間:10回実行した平均(秒))
    アルゴリズム100100010000100000100000010000000100000000
    Arrays.Sort0.000 0.000 0.000 0.001 0.004 0.025 0.205
    MasSort0.000 0.000 0.001 0.001 0.010 0.136 0.931
    MatSort0.000 0.000 0.000 0.002 0.008 0.109 1.483
    Merge Sort0.000 0.000 0.001 0.004 0.020 0.163 1.825
    In-place Merge Sort0.000 0.000 0.001 0.003 0.017 0.180 1.939
    Quick Sort (Median of 3)0.000 0.000 0.001 0.007 0.034 0.360 4.082
    Many Pivot Sort0.000 0.000 0.003 0.014 0.058 0.395 4.530
    Many Pivot Sort (3 Way)0.000 0.000 0.002 0.016 0.116 0.565 4.830
    Improved Merge Sort0.000 0.000 0.001 0.008 0.044 0.452 4.911
    Quick Sort0.000 0.000 0.001 0.040 0.069 0.506 5.385


    降順ソート済みデータ (時間:10回実行した平均(秒))
    アルゴリズム100100010000100000100000010000000100000000
    Arrays.Sort0.000 0.000 0.002 0.009 0.039 0.262 3.209
    Quick Sort (Median of 3)0.000 0.000 0.002 0.011 0.040 0.420 4.604
    Many Pivot Sort (3 Way)0.000 0.001 0.002 0.015 0.144 0.560 5.087
    Many Pivot Sort0.000 0.000 0.002 0.017 0.069 0.429 5.634
    Quick Sort0.000 0.000 0.002 0.019 0.067 0.556 5.979
    MatSort0.000 0.001 0.006 0.022 0.142 0.814 8.013
    MasSort0.000 0.001 0.003 0.014 0.085 0.770 10.533
    Improved Merge Sort0.000 0.001 0.007 0.019 0.119 1.685 17.254
    Merge Sort0.000 0.001 0.007 0.025 0.150 1.722 19.696
    In-place Merge Sort0.000 0.001 0.006 0.036 0.519 11.484 206.989


    全て同値キーデータ (時間:10回実行した平均(秒))
    アルゴリズム100100010000100000100000010000000100000000
    Many Pivot Sort0.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 Sort0.000 0.000 0.006 0.071 0.395 3.585 49.723
    MasSort0.000 0.001 0.010 0.029 0.369 4.010 57.535
    MatSort0.002 0.001 0.007 0.032 0.461 4.610 59.438
    Arrays.Sort0.001 0.000 0.006 0.041 0.405 4.547 69.795
    Merge Sort0.000 0.001 0.008 0.030 0.402 4.786 72.191
    Improved Merge Sort0.000 0.000 0.007 0.028 0.403 4.587 72.967
    In-place Merge Sort0.000 0.001 0.008 0.067 0.855 12.746 222.223


    ランダムデータ (比較回数:10回実行した平均(回))
    アルゴリズム100100010000100000100000010000000100000000
    Improved Merge Sort52785921192031524616185750882188781662521161713
    Merge Sort52785991192661525127185832792189437012521686000
    MasSort52786521206511525883186229002203267222522494443
    Arrays.Sort53286751203851534748186405032202472892530496049
    MatSort59292031258911599380191897632255373422596358506
    Many Pivot Sort (3 Way)50889411232191585771193643062288918712633723073
    Many Pivot Sort763121911530601885352224086012569008512914248341
    Quick Sort (Median of 3)763121911607182021684242400422849610513266912797
    Quick Sort672114351593452041510254092042987582283436000611
    In-place Merge Sort527111861715732250584278804543340720273880765565


    ソースファイル


     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 クイックソート(3つのメディアン・比較用)
    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ライセンスに基づき商用を含め自由にご利用いただけます。


    コンタクト


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

    home
  •  








    [an error occurred while processing this directive]