Median-of-3 Killer 系列
Musser によるイントロソートの原著によれば、Median-of-3 Killer 系列により、クイックソート内で３要素の中央値をピボットに選ぶ手続きの弱点を突いて、ソートコストを著しく増大させることができてしまう。
それを防ぐために、イントロソートでは再帰レベルに応じてヒープソートに移行させているわけであるが、一方、クイックソートの最近の実装では別の方法で Median-of-3 Killer 系列による攻撃を防いでいる。具体的には、要素数が40より多い場合に９要素の中央値(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 を使ったイントロソートを採用することにした。