13

(QuickSort:GeeksforGeeksを参照)

QuickSortの大枠を、

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high) {
    if (low < high) {
        pi = partition(arr, low, high)

        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    }
}

としたとき、partition()には、先述GeeksforGeeksのような

/* 以下 p1 と表記 */
partition (arr[], low, high) {
    pivot = arr[high]

    i = low - 1

    for (j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) { // ***
            i++
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high]
    return (i + 1)
}

// GeeksforGeeks からまるまる引用
// この *** 部分の比較を < に変更したものを p1' とする

というもの(iとjが共に前から後ろへ。VisuAlgo他いくつかのサイトで見かける)と、

/* 以下 p2 と表記 */
partition (arr[], low, high) 
{ 
    pivot = arr[high]

    i = low
    j = high - 1

    for ( ; ; ) {
        while (arr[i] < pivot) i++
        while (i < j && pivot < arr[j]) j--
        if (i >= j) break
        swap arr[i] and arr[j]
        i++
        j--
    }
    swap arr[i] and arr[high]
    return i
}

というもの(iは前から、jは後ろから)があるように見受けられます。

当方の環境で実験したところ、1000万要素などになると露骨にp1の方が遅くなります(比較回数は少なめだが交換回数が多い)。
これは前者のpartition()が間違って書かれているのでしょうか。
複数のサイトで誤りが放置されているとは考えにくいので実際は私に何か勘違いがあるのだと思います。ご指摘いただければ幸いです。


実験

(Core2Duo E4600, g++ 8.2.0 最適化なし, vector<int>, 乱数, メモリは全2GBで余力は0.8GB程度)

|     | 10^6 個 | 10^7 | 10^8  |
+-----+-------- +------+-------+
| p1' | 0.6 秒  | 14.6 | 953.3 |
| p2  | 0.4     |  4.5 |  51.1 |

なお p1 そのままを使うとさらに遅くなる
| p1  | 1.0     | 52.9 | 未計測|

使ったC++コード

  • 常駐ソフト等が悪さをしているのかと思いセーフモード起動で試したが同様
  • 最適化-O2を使っても同様。108件で208秒vs12秒
  • さらに化石PC(PentiumM 1.73GHz!)を引っぱり出して実験したが同様。107件で21秒vs6秒
  • コンパイラの違いかと思いVisual C++ 2010 Expressが入っていたので試したが同様。108件で270秒vs12秒
  • partition()呼び出し回数・swap回数をカウントしたところ異常な伸び方はしていない
|     |        10^6 個          |   10^7    |   10^8    |
+-----+-------------------------+-----------+-----------+
| p1' | 0.01億calls, 0.1億swaps | 0.1 , 1.1 | 1.0, 12.0 |
| p2  | 0.006      , 0.05       | 0.06, 0.7 | 0.6,  8.6 |

実験2: ソート対象の要素の重複具合について

[0..ARRAY_SIZE) をシャッフルしたユニークな配列の場合、定数倍っぽい差の出方に改善した(最適化-O2を使うとさらに差は縮まる)。

|     |10^6 |10^7 | 10^8 |
+-----+-----+-----+------+
| p1' | 0.6 | 6.8 | 79.6 |
| p2  | 0.4 | 4.5 | 51.5 |

[0..ARRAY_SIZE) の先頭何%かを同一要素にしてからシャッフルした配列の場合、重複を多くしていくとp1'の性能が劣化した

10^7 件 において

|     | 0.1%| 0.4% | 0.5%
+-----+-----+------+------
| p1' | 7.4 | 11.6 | クラッシュ(スタック溢れ?)
| p2  | 4.5 |  4.5 | 4.5

使ったコード断片


解決事項

  • 複数人による検証によるとアルゴリズム、コードに致命的誤りはない (聞きたかったことは解決)
  • p1 は同一要素含みの配列に弱い
5
  • 1
    Intel Xeon E3-1220v3(3.10GHz), g++ 7.3.0(-O2 を指定), array size = 10^9 で 上:110s, 下:100s という結果になりました。メモリ(RSS)は3.7G程度を使用しています。
    – user39889
    Commented 2019年1月27日 16:20
  • 2
    本題とは関係がない話ですが、そちらでお使いの C++ のソースコードに partition2 という関数があります。その中に while (pivot < arr[j]) j--; という部分があるのですが、ソート対象のベクタが、例えば、{3, 5, 2, 7, 4, 10, 9, 6, 8, 1} の場合(pivot はベクタの最後の要素)、最終的に j の値が -1 以下になってしまいます。つまり out-of-bounds access になっています(実行時に segmentation fault が発生する場合がありました)。g++ の場合ですと、コンパイル時に -D_GLIBCXX_DEBUG オプションを付加しておくと、実行時に out-of-bounds access を検出してくれます(もしくは memory sanitizer を利用するなど)。
    – user39889
    Commented 2019年1月27日 17:58
  • 1
    範囲外アクセスの件、修正しました
    – komatsuna
    Commented 2019年1月28日 14:09
  • 1
    i7-6700Kでi686-w64-mingw32-g++ (GCC) 7.4.0 だと -O2で quick1: 1.375000 sec quick2: 0.590000 sec Cygwinのg++ (GCC) 7.4.0だと quick1: 0.765000 sec quick2: 0.718000 sec とmingwだと顕著に差が出ました。不思議です。
    – zakki
    Commented 2019年1月30日 14:40
  • 1
    randomize()の実装をstd::mt19937にするとMinGWでも速度差出ませんし、randomize()の実装をMSVC互換の線形合同法の上位ビットにするとCygwinでも速度差出るので、qsortで計算量の増えるパターンになっているのかもしれません。
    – zakki
    Commented 2019年1月30日 16:01

4 件の回答 4

13
+50

クイックソートでは(ほぼ)ソート済みの配列や同一要素の配列に対して平均的なO(N log N)ではなくO(N^2)のワーストケースになります。
VCやMinGWではRAND_MAXが0x7fffしかないため10000000要素の配列では305個程度同じ値があり、性能の劣化が起こります。

void randomize(vector<int> &arr) {
  std::mt19937 mt(0);
  uniform_int_distribution<int> dist(0, 32768);
    for(int i = 0; i < ARRAY_SIZE; ++i) {
      arr[i] = dist(mt);
    }
}

やさらに極端に

void randomize(vector<int> &arr) {
  fill_n(arr.begin(), ARRAY_SIZE, 0);
}

とすると他の方の回答にあるLinux環境でも再現するはずです。

そういった同一要素を多数含む配列の場合、partition2()はほぼ1:1で2等分しO(N log N)で処理できますが、partition()はlowかhighに近いインデックスで分割し1:N-1の分割しかできません。結果としてquickSort()はO(N^2)に近くなってしまいます。

例えば同一値が7要素の [0, 0, 0, 0, 0, 0, 0] をソートする場合、p1ではピボット値以外の要素以外はピボット値以上側に割り振られ21回比較が発生します。

[] (0) [0, 0, 0, 0, 0, 0] // 比較6回
[] (0) [[] (0) [0, 0, 0, 0, 0]] // 比較5回
[] (0) [[] (0) [[] (0) [0, 0, 0, 0]]] // 比較4回
[] (0) [[] (0) [[] (0) [[] (0) [0, 0, 0]]]] // 比較3回
[] (0) [[] (0) [[] (0) [[] (0) [[] (0) [0, 0]]]]] // 比較2回
[] (0) [[] (0) [[] (0) [[] (0) [[] (0) [[] (0) [0]]]]]] // 比較1回

p2では両端から挟み込むので、ピボット位置が中央にきて比較16回で済みます。

[0, 0, 0, 0, 0, 0, 0] // 比較8回
[0, 0, 0] 0 [0, 0, 0] // 比較4+4回
[[0] 0 [0]] 0 [[0] 0 [0]]

同一値についてはp2で対応可能ですが、[0, 1, 2, 3]や[3, 2, 1, 0]のような入力に対してはp1もp2もうまくいかないので実用上はさらに工夫が必要されていることが多いようです。

3
  • 乱数の範囲を0...0x7FFFにすることにより、こちらでも「上」「下」の顕著な性能差を観測することができました。きちんとした解析は出来ていませんが、QuickSortのワーストケースに近い振る舞いをしやすくなるのだろうと言うのは納得です。なぜ「下」のアルゴリズムはそのような影響を受け難いのかについて何らかの知見をいただけるとさらに良い回答になるかと思います。
    – OOPer
    Commented 2019年1月31日 12:50
  • なるほど!当方でも簡単に実験してみましたところ(追記しました)、要素の重複具合はかなり関係していそうです
    – komatsuna
    Commented 2019年1月31日 22:03
  • 2
    実例を追記しました。ソート済み入力も考えるとさらに難しいですね。
    – zakki
    Commented 2019年2月1日 5:01
4

当方の環境では要素数を1億にしても速度差はせいぜい10%前後でした。「下」の方が有意に早かったのですが、交換が発生する回数をカウントするためのコードを付け加えた場合など、「下」の方が遅くなることもありました。使用する言語やCPU、要素数や要素の分布によっても、結果は変動するだろうと思います。

「上」の方では、配列全体を舐めて、pivotより小さな数に対して必ず交換が発生するのに対して、「下」の方では配列を前と後ろから舐めて、pivotより大きな数が前側/pivotより小さな数が後ろ側にあるときだけ交換が発生しします。

pivotがうまく中央値になったとして(常に「最後の要素」では、そううまくいきませんが)、分割したい部分配列のサイズをNとすると、前者がN/2(前半に入る要素数そのまま), 後者がN/4程度(前半に入る要素数の平均して2つに1つは交換が必要)の期待値で交換が発生することになります。(実際には平均してももうちょっと大きな違いが発生しましたが。)

その代わり比較や条件分岐の数が少ない訳ですから、交換のコストより比較や条件分岐のコストが相対的に高いなら「上」が有利、交換のコストの方が高いなら「下」が有利と言えるかと思います。

これは前者のpartition()が間違って書かれているのでしょうか。

「上」の方のアルゴリズムを試してみて、なにか間違った答えが出たことがあるでしょうか。平均してO(n*log n)の計算量でソーティングが完了することには変わりはありません。ご自分の環境に応じて、より良い特性を示す方のアルゴルズムを採用されれば良いことだろうと思います。


追記
zakkiさんの追記された部分まで読めばほぼ解決かと思うのですが、私の場合何度も考え直さないとわからなかったので、もしかして中にはご理解が深まる方もおられるかもしれないと言うことで、一応考えたことを整理しておきます。

実はp1(「上」)とp2(「下」)との間には分割後の状態に若干の差異があります。

p1

 lo             pi                   hi
|    <pv       |pv|        ≧pv         |

(pvがピボット値。p1の交換条件のarr[j] < pivotに等号をつけて<=にするとちょっと様子が変わるのですが、簡単のためそちらは省略。)

p2

 lo                 pi               hi
|      ≦pv         |pv|     ≧pv        |

p1の分割後は、pvと同位の要素は必ずpiよりもhi側に固まるのに対して、p2ではpvと同位の要素がpiよりlo側にもhi側にも現れることになります。(p2でもp1と同じように、pvと同位の要素がhi側に固まる可能性も無いでは無いが、極めてまれ。)

これはpvとして最小値を選んでしまった場合にはさらに顕著で、

p1

 pi
(lo)                                 hi
|pv|               ≧pv                 |

p1の方では必ずQuickSort的に最悪の分割となるのに対して、p2の方は、

p2

 lo      pi                          hi
|  =pv  |pv|           ≧pv             |

と言う分割になり、たとえpvに最小値を選んでしまった場合でも(pvと同位の要素が多数あるならば)、QuickSort的に最悪の分割になることは滅多に起こらないわけです。

部分配列の要素が全部同じ値になるまで分割が進むと(1億要素に対し0...0x7FFFの乱数を割り当てると同じ値の要素が3000件ほどあると期待される)、p1では常に最悪分割になるのに対し、p2では常にほぼ中央の最善分割になると言うのはzakkiさんの実例でよくわかるだろうと思います。


と言うわけで、同位の値が発生するなんてことは実際のソーティングではよくあることなのに、考えが至らなかったのはお恥ずかしい限りです。しっかりと問題点を把握して、実例を交えて解説していただいた、zakkiさんには改めて感謝いたします。(upvoteが1回しか出来ないのが残念です。)

7
  • 当方での試行結果を追記しました。化石CPUでアレですが「ここまで差がつくだろうか?」というのを疑問に思い今回質問した次第です。「私の環境でswapのコストが高いことに起因している。実装自体は両者とも正しい。」と捉えておいて大丈夫ですかね?
    – komatsuna
    Commented 2019年1月26日 14:16
  • 1
    @komatsuna さん、大丈夫ではないような差がついていますね。g++での「上」アルゴリズムのコーディングに間違いがある可能性もありそうです。(私は最初「上」アルゴリズムのコードを間違えてしまい、随分悩んでしまいました。)Core i7 3.2GHz Swift 4.2最適化あり1億件ランダムInt(64bit)で、上が9.8秒、下が8.7秒くらいです。g++のコードを示していただければ、修正すべき点を見つけられるかもしれません。
    – OOPer
    Commented 2019年1月26日 14:25
  • ideone.com/Ehhq0f に書きました。
    – komatsuna
    Commented 2019年1月27日 0:32
  • 1
    @komatsuna さん、コードのご提示ありがとうございます。ただ、大して長いコードでもないので、本文中に直接記入していただいた方が良いように思います。将来リンク切れの心配もなくなりますし。ご提示のコード、範囲外アクセスになる可能性があったので、一箇所だけ書き換えさせていただきました。while (pivot < arr[j]) j--;while (i < j && pivot < arr[j]) j--;元のままだとjlowより小さい値になってしまい、時には0より小さくなる可能性もあります。(そう言う意味では「下」アルゴリズムは若干不完全。)こちらの環境はclang(Fastest, Smallest)ですが、1億件に変更して実行結果は、quick1: 7.642276 sec/quick2: 7.591940 sec。時にはquick2の方が時間がかかる時もあり、私のSwiftコードよりもっと差が少ないと言う結果になりました。「300経っても終わらず」の時からコードを全く修正していないのであれば、そちらの実行環境に何らかの原因がありそうです。メモリが極端に少ない(32bitintが1億件だと約400MB必要)とかはありますでしょうか?
    – OOPer
    Commented 2019年1月27日 1:39
  • 1
    Ubuntu 16.04を入れたマシンが2GBだったので試してみました。quick1: 18.547525 sec/quick2: 17.622566 sec(Ubuntu 16.04/Celeron [email protected],-O2)、やはりそれほど顕著な差は出ないですね。Core i7マシンとほぼクロック数比例の違いしか出なかった感じです。
    – OOPer
    Commented 2019年1月27日 15:29
2

Quick Sortは1960年にアントニー・ホーアさんが発表したものです。Communications of the ACM Volume 4 Issue 7, July 1961 Page 321に掲載されています。

記述はPascal言語ですのでgo toが多用されるなど細部は異なりますが、p2に近い実装になっていました。


p1の出典は分かりませんが、スワップコスト(intでなく大きな構造体など)や配列サイズ(大規模配列でなく任意のサイズで良好な性能が得られるなど)も踏まえて改良されたものではないでしょうか。

2

余談ついでに にはテンプレートライブラリで std::sort が実装されています。
https://cpprefjp.github.io/reference/algorithm/sort.html

より古いものは「平均して」 O(N log N) と規定されているので、最悪オーダーが O(N*N) となる quicksort で実装されていても要件に合致します。

で「平均して」の文言が削除され、つまり常に O(N log N) とされました。これを実現するために、ほぼすべての 処理系は イントロソート を実装しているようです(ってかホントは逆で、イントロソートの有用性が広く知られたので「平均して」を取ることにしたらしい)

イントロソートは途中までクイックソート、再帰が深くなったらヒープソートに切り替える(と、クイックソートの最悪状況を避けられる)というアルゴリズムです。実際に gcc/cygwin の実装を見てみたところ、イントロソートで「ほぼソート」し、挿入ソートするという方法を取っていました。挿入ソートは「ほぼソート」済み状態のデータに対してきわめて高速であることが知られています。各種アルゴリズムの良いとこ取り+デバッグ済みなので std::sort をぜひ使いたいところです。

ちなみに、乱数の与え方を a[i]=xor128();a[i]=xor128()&0x7FFF; と2つのパターンを用意して std::sort に渡したところ、重複が多いであろう 15bit 値のほうが早く終了しました。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。