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 | 未計測|
- 常駐ソフト等が悪さをしているのかと思いセーフモード起動で試したが同様
- 最適化-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 は同一要素含みの配列に弱い
Intel Xeon E3-1220v3(3.10GHz)
,g++ 7.3.0
(-O2
を指定), array size = 10^9 で 上:110s, 下:100s という結果になりました。メモリ(RSS)は3.7G程度を使用しています。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 を利用するなど)。