####newlib・glibcより高速なqsortクイックソート qs15 qs16
これまで長期間に渡り、実用的なqsortとして、newlib・glibc の qsort が
使われて来ました。そろそろより実用的で高速なqsortに置き換えても
良い時期ではないでしょうか。
newlib・glibc の qsort は、ソート条件（キー値の分布・要素数・要素サイズ）により
速い/遅いが入れ替わります。
ほどんど全てのソート条件で、 newlib・glibc のどちらよりも速い
qsort (qs15 , qs16) を作成しました。
ただし、意図的に最悪計算時間になるように作られたソート対象配列では
glibc の qsort が最速(または、比較関数の呼び出し回数が最小)となります。なぜなら、
glibc の qsort の実体はマージソートだからです。
qs15・qs16は、以前に作成したqs12・qs13より
コンパクト(バイナリコードで半分の大きさ）になっています。
qs15は、基本的にはクイックソート
qs9 (https://qiita.com/t-kawa/items/99408891b18bd1f87ae6) として動きます。
ただし、間接ソートが速いと予測したときは、間接ソートを行います。
間接ソートとは、各要素へのポインタ配列を作り、これをソートすることです。
qs16は、qs15・直接mps・間接mpsから適切な手法を予測してソートを行います。
mpsとは、サンプル(m個)をソートして、区間(2m+1個)のそれぞれの先頭位置を計算して、
その区間内の位置に各要素を移動して、最後にソートが必要な区間(m+1個)をソートします。
newlib・glibc・qs15・qs16の比較回数・実行時間を以下に示します。
qs_glibcは、glibcのqsortを実験用に改造したものです。
使用したプログラムは https://github.com/kawamura1953/quick-sort にあります。
----------------- benchmark.txt begin --------------------
キー種別:同値なし 要素数:1万個 要素サイズ:8,80,1000byte
qsort d=-3 e=10000 s=8 R5000 M000:000:000:0: c=136795 683975303 T=10.22 204
qsnewlib d=-3 e=10000 s=8 R5000 M000:000:000:0: c=136795 683975303 T=10.42 208
qs_glibc d=-3 e=10000 s=8 R5000 M000:000:000:0: c=120451 602257294 T=12.15 243
qs15c2 d=-3 e=10000 s=8 R5000 M120:580:180:0: c=128064 640321766 T=9.66 193
qs16e2 d=-3 e=10000 s=8 R5000 M120:580:180:0: c=128064 640321766 T=9.64 193
qsort d=-3 e=10000 s=80 R5000 M000:000:000:0: c=136795 683975303 T=14.27 285
qsnewlib d=-3 e=10000 s=80 R5000 M000:000:000:0: c=136795 683975303 T=14.21 284
qs_glibc d=-3 e=10000 s=80 R5000 M000:000:000:0: c=120451 602257294 T=16.38 328
qs15c2 d=-3 e=10000 s=80 R5000 M120:580:180:0: c=128064 640321766 T=11.36 227
qs16e2 d=-3 e=10000 s=80 R5000 M120:580:180:0: c=128064 640321766 T=11.37 227
qsort d=-3 e=10000 s=1000 R1000 M000:000:000:0: c=136826 136826241 T=16.04 1604
qsnewlib d=-3 e=10000 s=1000 R1000 M000:000:000:0: c=136826 136826241 T=16.11 1611
qs_glibc d=-3 e=10000 s=1000 R1000 M000:000:000:0: c=120450 120450635 T=7.82 782
qs15c2 d=-3 e=10000 s=1000 R1000 M120:580:180:0: c=128086 128086595 T=7.41 741
qs16e2 d=-3 e=10000 s=1000 R1000 M120:580:180:0: c=128086 128086595 T=7.49 749
キー種別:100種 要素数:1万個 要素サイズ:8,80,1000byte
qsort d=100 e=10000 s=8 R10000 M000:000:000:0: c=62873 628731716 T=8.74 87
qsnewlib d=100 e=10000 s=8 R10000 M000:000:000:0: c=62873 628731716 T=9.25 92
qs_glibc d=100 e=10000 s=8 R10000 M000:000:000:0: c=120211 1202115137 T=22.04 220
qs15c2 d=100 e=10000 s=8 R10000 M120:580:180:0: c=60846 608464923 T=8.72 87
qs16e2 d=100 e=10000 s=8 R10000 M120:580:180:0: c=60846 608464923 T=8.58 86
qsort d=100 e=10000 s=80 R10000 M000:000:000:0: c=62873 628731716 T=14.52 145
qsnewlib d=100 e=10000 s=80 R10000 M000:000:000:0: c=62873 628731716 T=14.82 148
qs_glibc d=100 e=10000 s=80 R10000 M000:000:000:0: c=120211 1202115137 T=29.34 293
qs15c2 d=100 e=10000 s=80 R10000 M120:580:180:0: c=60846 608464923 T=10.86 109
qs16e2 d=100 e=10000 s=80 R10000 M120:580:180:0: c=60846 608464923 T=10.70 107
qsort d=100 e=10000 s=1000 R2000 M000:000:000:0: c=62947 125895777 T=24.94 1247
qsnewlib d=100 e=10000 s=1000 R2000 M000:000:000:0: c=62947 125895777 T=25.05 1253
qs_glibc d=100 e=10000 s=1000 R2000 M000:000:000:0: c=120212 240424496 T=14.79 739
qs15c2 d=100 e=10000 s=1000 R2000 M120:580:180:0: c=60879 121759817 T=12.26 613
qs16e2 d=100 e=10000 s=1000 R2000 M120:580:180:0: c=61391 122782892 T=11.86 593
キー種別:2種 要素数:1万個 要素サイズ:8,80,1000byte
qsort d=2 e=10000 s=8 R20000 M000:000:000:0: c=15020 300410541 T=4.07 20
qsnewlib d=2 e=10000 s=8 R20000 M000:000:000:0: c=15020 300410541 T=4.43 22
qs_glibc d=2 e=10000 s=8 R20000 M000:000:000:0: c=94725 1894516279 T=30.65 153
qs15c2 d=2 e=10000 s=8 R20000 M120:580:180:0: c=15052 301043181 T=3.68 18
qs16e2 d=2 e=10000 s=8 R20000 M120:580:180:0: c=15052 301043181 T=3.73 19
qsort d=2 e=10000 s=80 R20000 M000:000:000:0: c=15020 300410541 T=10.11 51
qsnewlib d=2 e=10000 s=80 R20000 M000:000:000:0: c=15020 300410541 T=10.44 52
qs_glibc d=2 e=10000 s=80 R20000 M000:000:000:0: c=94725 1894516279 T=42.70 213
qs15c2 d=2 e=10000 s=80 R20000 M120:580:180:0: c=15052 301043181 T=4.51 23
qs16e2 d=2 e=10000 s=80 R20000 M120:580:180:0: c=15052 301043181 T=4.46 22
qsort d=2 e=10000 s=1000 R3000 M000:000:000:0: c=15020 45060726 T=22.21 740
qsnewlib d=2 e=10000 s=1000 R3000 M000:000:000:0: c=15020 45060726 T=22.07 736
qs_glibc d=2 e=10000 s=1000 R3000 M000:000:000:0: c=94732 284197358 T=19.47 649
qs15c2 d=2 e=10000 s=1000 R3000 M120:580:180:0: c=15084 45253464 T=6.65 222
qs16e2 d=2 e=10000 s=1000 R3000 M120:580:180:0: c=15084 45253464 T=6.61 220
キー種別:10種 要素数:1万,10万,100万個 要素サイズ:400byte
qsort d=10 e=10000 s=400 R2000 M000:000:000:0: c=30277 60554039 T=7.13 356
qsnewlib d=10 e=10000 s=400 R2000 M000:000:000:0: c=30277 60554039 T=7.36 368
qs_glibc d=10 e=10000 s=400 R2000 M000:000:000:0: c=116416 232833027 T=10.08 504
qs15c2 d=10 e=10000 s=400 R2000 M120:580:180:0: c=29649 59299425 T=4.63 232
qs16e2 d=10 e=10000 s=400 R2000 M120:580:180:0: c=29712 59424938 T=4.27 214
qsort d=10 e=100000 s=400 R200 M000:000:000:0: c=301637 60327445 T=9.59 4796
qsnewlib d=10 e=100000 s=400 R200 M000:000:000:0: c=301637 60327445 T=9.22 4610
qs_glibc d=10 e=100000 s=400 R200 M000:000:000:0: c=1479728 295945709 T=16.25 8128
qs15c2 d=10 e=100000 s=400 R200 M120:580:180:0: c=294954 58990860 T=5.32 2660
qs16e2 d=10 e=100000 s=400 R200 M120:580:180:0: c=292624 58524925 T=5.12 2558
qsort d=10 e=1000000 s=400 R20 M000:000:000:0: c=2980287 59605743 T=9.47 47345
qsnewlib d=10 e=1000000 s=400 R20 M000:000:000:0: c=2980287 59605743 T=9.56 47815
qs_glibc d=10 e=1000000 s=400 R20 M000:000:000:0: c=17952145 359042905 T=21.32 106615
qs15c2 d=10 e=1000000 s=400 R20 M120:580:180:0: c=2940213 58804262 T=5.58 27925
qs16e2 d=10 e=1000000 s=400 R20 M120:580:180:0: c=2910960 58219214 T=5.22 26125
================= benchmark.txt end ====================
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です
qsortのベンチマークテストの要領
１．github.com/kawamura1953/quick-sort から次の７つのファイルをダウンロードする。
qs15c2.c
qs16e2.c
mm88k.c.c
qsnewlib.c
qs_glibc.c
main_prog.c
benchmark.sh
２．benchmark.sh を実行する。実行結果は benchmark.txt へ書き込まれる。
main_prog.c は benchmark.sh の中でコンパイル・実行されます。
これの引数と出力の説明は、Readme2.txtを参照。
３．その他のファイル
Readme.txt : このファイル
Readme2.txt : より詳細な説明
bench-sample.txt : ベンチマークテスト結果の例