Median-of-3 Killer 系列
Musser によるイントロソートの原著によれば、Median-of-3 Killer 系列により、クイックソート内で3要素の中央値をピボットに選ぶ手続きの弱点を突いて、ソートコストを著しく増大させることができてしまう。
それを防ぐために、イントロソートでは再帰レベルに応じてヒープソートに移行させているわけであるが、一方、クイックソートの最近の実装では別の方法で Median-of-3 Killer 系列による攻撃を防いでいる。具体的には、要素数が40より多い場合に9要素の中央値(Median-of-9)をピボットに選ぶようにしている。
Median-of-3 Killer 系列の生成の仕方は以下の通りである。
const int n = 1000000; double *x = new double[n]; int i; /* Median-of-3 killer sequences: n=2k: 1 k+1 3 k+3 5 ... 2k-3 k-1 2k-1|2 4 6 ... 2k-2 2k */ for (i=1; i<=n; i++) x[i-1] = (i<=n/2) ? ((i%2)?i:(n/2+i-1)) : ((i-n/2)*2);
実際に Median-of-3 Killer 系列でベンチマークを取ってみよう。
qsort0_r
: C によるクイックソート (自作)qsort1_r
: C によるクイックソートと Median-of-3 (自作)qsort
,qsort_b
: C による Snow Leopard におけるイントロソートと Median-of-9qsort_r
: C によるクイックソートと Median-of-9 (自作)introsort1_r
: C によるイントロソートおよび Median-of-3 (自作)introsort_r
,pintrosort_r
: C によるイントロソートおよび Median-of-9 (自作)quick_sort0
: C++ によるクイックソートquick_sort1
: C++ によるクイックソートと Median-of-3sort
: C++ STL によるイントロソートと Median-of-3sequential_sort
,parallel_sort
: C++ によるイントロソートと Median-of-9 (自作)
手続き | 秒 |
qsort0_r(x, n, sizeof(x[0]), NULL, d_rcmp_r) | 0.999239 |
qsort1_r(x, n, sizeof(x[0]), NULL, d_rcmp_r) | 0.169529 |
qsort(x, n, sizeof(x[0]), d_rcmp) | 0.102953 |
qsort_r(x, n, sizeof(x[0]), NULL, d_rcmp_r) | 0.126576 |
qsort_b(x, n, sizeof(x[0]), d_rcmp_b) | 0.103214 |
introsort1_r(x, n, sizeof(x[0]), NULL, d_rcmp_r) | 0.152328 |
introsort_r(x, n, sizeof(x[0]), NULL, d_rcmp_r) | 0.096868 |
psort_b(x, n, sizeof(x[0]), d_rcmp_b) | 0.0499592 |
pintrosort_r(x, n, sizeof(x[0]), NULL, d_rcmp_r) | 0.0511229 |
quick_sort0(x, x+n, greater<double>()) | 39.2215 |
quick_sort1(x, x+n, greater<double>()) | 19.6233 |
sort(x, x+n, greater<double>()) | 0.0951362 |
sequential_sort(x, x+n, greater<double>()) | 0.027447 |
parallel_sort(x, x+n, greater<double>()) | 0.0134389 |
結果によると、イントロソートのようにヒープソートに移行するからといって Median-of-9 による対策をしていないと、無対策の quick_sort0
, quick_sort1
ほどではないにせよ性能低下は免れないようだ。よって、sort_r-20100723.tar.bz2 にはイントロソートにおいても Median-of-9 を使ったイントロソートを採用することにした。