より高速なqsortクイックソート qs19
2019年にqsort(qs15)を公開しました。
https://qiita.com/t-kawa/items/631564a703e20dceed24
2020～2021年に安定なクイックソートsqsort(ss18)を公開しました。
https://qiita.com/t-kawa/items/dc15243e160a4af90518
qsort は timsort や sqsort より高速です。( timsort < sqsort < qsort )
ただし、qsortは非安定です。
sqsort開発の過程で、
「安定性がなくても、とにかく高速なソートが必要だ」
と感じました。
今回、sqsortで使用した方法で、qs15より約5%高速なqs19を開発しました。
qsort(qs19)のソースコード・ベンチマークプログラムなどは
http://ww51.tiki.ne.jp/~srr-cake/qsort/qs19/ にあります。
qsort19.cのソースコードは約500行です。
timsort ( 約1300行 ) よりかなりコンパクトです。
言語Cの標準ライブラリのqsortと今回のqsort19の処理時間を
測定したものを以下に記載します。
まだまだ多くの標準ライブラリのqsortが低速であると思われます。
ご興味がおありの方は、上記のベンチマークプログラムを動かして
その結果をこのQiitaのコメント欄に掲示して頂けないでしょうか。
----------------- benchmark.txt begin --------------------
キー:同値なし 要素:1万個 要素サイズ:8または4,20,80,1000byte
qsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=136763 547054643 T=3.75 94
qsort19 d=-3 e=10000 s=8 R4000 M120:580:000:0: c=128058 512234423 T=3.27 82
qsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=136748 410244182 T=4.73 158
qsort19 d=-3 e=10000 s=20 R3000 M120:580:000:0: c=128053 384160670 T=3.00 100
qsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=136748 410244182 T=3.61 120
qsort19 d=-3 e=10000 s=80 R3000 M120:580:000:0: c=128053 384160670 T=3.31 110
qsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=136776 82066150 T=3.47 578
qsort19 d=-3 e=10000 s=1000 R600 M120:580:000:0: c=128090 76854257 T=1.69 281
キー種別:100種 要素:1万個 要素サイズ:8または4,20,80,1000byte
qsort d=100 e=10000 s=8 R6000 M000:000:000:0: c=62894 377366851 T=2.44 41
qsort19 d=100 e=10000 s=8 R6000 M120:580:000:0: c=60849 365096092 T=2.28 38
qsort d=100 e=10000 s=20 R3000 M000:000:000:0: c=62889 188668276 T=2.52 84
qsort19 d=100 e=10000 s=20 R3000 M120:580:000:0: c=60841 182523251 T=1.36 45
qsort d=100 e=10000 s=80 R4000 M000:000:000:0: c=62897 251590917 T=2.39 60
qsort19 d=100 e=10000 s=80 R4000 M120:580:000:0: c=60844 243378572 T=2.06 52
qsort d=100 e=10000 s=1000 R500 M000:000:000:0: c=62849 31424752 T=2.19 438
qsort19 d=100 e=10000 s=1000 R500 M120:580:000:0: c=60866 30433364 T=1.16 231
キー種別:2種 要素:1万個 要素サイズ:8または4,20,80,1000byte
qsort d=2 e=10000 s=8 R30000 M000:000:000:0: c=15020 450617436 T=2.81 9
qsort19 d=2 e=10000 s=8 R30000 M120:580:000:0: c=15051 451545559 T=2.42 8
qsort d=2 e=10000 s=20 R13000 M000:000:000:0: c=15019 195259918 T=4.09 31
qsort19 d=2 e=10000 s=20 R13000 M120:580:000:0: c=15051 195672706 T=1.20 9
qsort d=2 e=10000 s=80 R12000 M000:000:000:0: c=15019 180239524 T=2.44 20
qsort19 d=2 e=10000 s=80 R12000 M120:580:000:0: c=15051 180619742 T=1.22 10
qsort d=2 e=10000 s=1000 R1200 M000:000:000:0: c=15020 18024163 T=2.90 242
qsort19 d=2 e=10000 s=1000 R1200 M120:580:000:0: c=15082 18098625 T=0.84 70
キー:同値なし 百～百万要素 要素サイズ:200byte
qsort d=-3 e=100 s=200 R400000 M000:000:000:0: c=644 257805086 T=3.30 1
qsort19 d=-3 e=100 s=200 R400000 M120:580:000:0: c=605 242260779 T=2.44 1
qsort d=-3 e=1000 s=200 R28000 M000:000:000:0: c=10064 281797331 T=3.35 12
qsort19 d=-3 e=1000 s=200 R28000 M120:580:000:0: c=9362 262156451 T=2.33 8
qsort d=-3 e=10000 s=200 R2000 M000:000:000:0: c=136727 273455402 T=3.25 162
qsort19 d=-3 e=10000 s=200 R2000 M120:580:000:0: c=128089 256178193 T=2.45 123
qsort d=-3 e=100000 s=200 R120 M000:000:000:0: c=1729580 207549609 T=3.00 2500
qsort19 d=-3 e=100000 s=200 R120 M120:580:000:0: c=1626865 195223804 T=2.77 2305
qsort d=-3 e=1000000 s=200 R11 M000:000:000:0: c=20994830 230943134 T=3.33 30245
qsort19 d=-3 e=1000000 s=200 R11 M120:580:000:0: c=19665513 216320653 T=3.08 27982
================= benchmark.txt end ====================
qsort ：ベンチマークテスト実行の計算機上の C ライブラリの qsort
qsort19 ：今回公開した qsort19の qsort
d=キー種類 (d=-3は、ユニーク乱数。d=kは、rand()%k でキーを算出。
e=要素数 s=要素サイズ R繰返し回数 c=比較回数/R T=処理秒数
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です