松のページ ソート


 





広告






twitter


掲示板

FeedWind
      

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

概要


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

  • Many Pivot Sort クイックソートのピボット値選択方法改善アルゴリズム
  • MasSort メモリの操作回数低減を狙ったマージソートの改善アルゴリズム
  • MatSort 作業領域のメモリ使用料量削減を狙ったマージソートの改善アルゴリズム(MasSort等、他のマージソート系アルゴリズムを内部的に併用する)

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

     MatSortは一般的なマージソートと比較して作業領域を数分の1程度に縮小しても、元のマージソートよりも高速となる場合もある。作業領域サイズをソート対象の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 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

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

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

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

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

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

     計算量は通常のマージソートと同様 O(N log2 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では作業領域のサイズは任意に指定できる。これは時間と空間のトレードオフとなる。

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

    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, 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 SortMasSortMatSort
    (1/10)
    MatSort
    (1/100)
    Arrays.SortMergeSortQuickSortQuickSort
    (Median 3)
    1000.00020.00040.00020.00030.00020.00050.00010.0002
    10000.00020.00090.00070.00070.00070.00070.00020.0002
    100000.00650.00670.00680.00670.00670.00890.00540.0064
    1000000.07010.03170.03230.03280.04030.0320.05610.0695
    10000000.3530.36010.44020.50550.42080.39560.36340.3609
    100000003.21144.11224.34315.55164.80034.79763.72653.6786
    10000000043.209362.543358.960568.251372.026771.043250.907852.5126

    昇順ソート済み配列 結果は10回実行した平均 (秒)
    配列サイズMany Pivot SortMasSortMatSort
    (1/10)
    MatSort
    (1/100)
    Arrays.SortMergeSortQuickSortQuickSort
    (Median 3)
    1000.00010.00020.00010.000200.00020.00010.0001
    10000.00030.00010.00020.00010.00020.00020.00010.0002
    100000.00360.00060.00030.00050.00040.00080.00130.0014
    1000000.03350.00120.00150.00080.00070.00530.01370.0338
    10000000.07690.01040.00720.01030.00390.01830.0770.0724
    100000000.55630.14730.09670.05970.02570.16910.53990.5659
    1000000005.89781.27191.40330.91610.21291.89915.9896.1085

    降順ソート済み配列 結果は10回実行した平均 (秒)
    配列サイズMany Pivot SortMasSortMatSort
    (1/10)
    MatSort
    (1/100)
    Arrays.SortMergeSortQuickSortQuickSort
    (Median 3)
    10000.000100.00020.00020.00020.00010.0001
    10000.00030.00040.00040.00020.00030.00060.00040.0003
    100000.0030.00510.00580.00540.0020.00750.00310.0028
    1000000.02910.02010.01660.01140.00870.02450.02150.0293
    10000000.09730.08380.12850.07540.04060.14330.06640.0807
    100000000.58820.74410.79311.37920.27461.66920.57420.5746
    1000000006.200412.99237.994610.35313.238119.78386.08086.1278

    全て同じキー値の配列 結果は10回実行した平均 (秒)
    配列サイズMany Pivot SortMasSortMatSort
    (1/10)
    MatSort
    (1/100)
    Arrays.SortMergeSortQuickSortQuickSort
    (Median 3)
    100000.00010.00020.00010.00010.00020.0002
    10000.00030.00020.00010.000300.00020.00040.0002
    100000.00650.00040.00080.00110.00020.00120.00690.007
    1000000.02650.00120.00410.00370.00070.00640.02180.0275
    10000000.07750.0110.01230.0170.00410.02960.06770.0833
    100000000.60970.1470.15310.09940.0270.30270.78590.7923
    1000000006.38591.22741.76021.3780.22633.66069.03539.0929

    ランダム配列(比較の回数) 結果は10回実行した平均 (回)
    配列サイズMany Pivot SortMasSortMatSort
    (1/10)
    MatSort
    (1/100)
    Arrays.SortMergeSortQuickSortQuickSort
    (Median 3)
    100683.1526.8591.8887532.2526.8671.7683.1
    100011069.88651.79203.111996.48675.18598.81143511069.8
    10000143303.7120650.6125890.8151684.5120385.2119265.6159345159190.9
    1000001795610.41525882.81599380.41851914.21534747.71525126.62041509.52022463.4
    100000021560342.918622899.519189763.221928149.118640503.118583279.225409203.525019783.8
    10000000247390458.3220326722225537341.8251229532.4220247288.9218943701.3298758227.9300010878.4
    10000000028208949472522494442.625963585062848689510.72530496048.52521685999.53436000610.83427142947.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ライセンスに基づき商用を含め自由にご利用いただけます。


    コンタクト


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

    home
    
  •  








    [an error occurred while processing this directive]