以前報告した２つのクイックソート ss18 と qs19 を改良したので報告します。
主な変更点は、安全性のための変更と、再帰呼び出しへの書き換えです。
qsort20(qs20)(qs19を改良) は、従来のqsortに比べて 1.1～2 倍高速です。そして、安全です。
sqsort(ss21)(ss18を改良) は、timsort よりも 1.7～5 倍高速です。そして、安定・安全です。
以下では、
安定 とは、「キー値が同じ要素は、ソートの前後でその順序を維持する」こととします。
安全 とは、「悪意のある配列により、異常に長いソート時間を発生させることが不可能」
なこととします。
qsort20・sqsort では「安全」を実現するために、
clock()関数を再現性のない乱数発生器として使用し、乱数を用いてピボットを決定します。
これにより、理論上の最悪計算時間$O(n^2)$は変化しませんが、
「悪意のある配列を作ることは不可能」となります。
ただし、qsort20 において、安全性の機能を発動するための
大域変数 _QS_RNDM の初期値は 0 です。
このため、_QS_RNDM=1; を実行するまで、この機能は発動しません。
なぜなら、この機能を発動すると、同じ内容の配列をソートしても、
ソート結果が異なることがあるからです。
この現象は、キー値が同じ要素を持つ配列で現れます。
そのため、プログラムが「安全性」を必要とする場合にのみ、
qsort20 を呼び出すプログラムのデバッグが終わったあとで、
_QS_RNDM=1; を追加して下さい。
追加の後、プログラムの動作が変わるようであれば、
プログラムに問題があることになります。
一方、sqsort では、常にこの機能が発動しています。
なぜなら、sqsort は「安定性」があるので、
キー値が同じ要素を持つ配列をソートしても、常にソート結果が同じだからです。
従来のqsortとtimsortを含めた４種類のソートを比較すると次の表のようになります。
| timsort | sqsort | qsort20 | 従来qsort | |
|---|---|---|---|---|
| 速さ | △ | ◎ | ◎ | ○ |
| 作業領域 | △ | △ | ◎ | ◎ |
| 安定性 | ○ | ○ | × | × |
| 安全性 | ◎ | ○ | ○ | × |
| 大きさ | × | ○ | ○ | ◎ |
qsort20 のソースコード・ベンチマークプログラムは
https://github.com/kawamura1953/qsort20 にあります。
sqsort・timsort のソースコード・ベンチマークプログラムは
https://github.com/kawamura1953/sqsort にあります。
以下に、上の４種類のベンチマークテストの一部を掲載します。
各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です 。
キー:同値なし 要素:1万個 要素サイズ:8,20,80,1000byte
my_qsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=136763 547054643 T=3.75 94
qsort20 d=-3 e=10000 s=8 R4000 M120:580:000:0: c=128053 512215278 T=3.35 84
sqsort d=-3 e=10000 s=8 R4000 M120:009:018:0: c=141431 565726225 T=3.19 80
timsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=120391 481564348 T=5.41 135
my_qsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=136748 410244182 T=4.73 158
qsort20 d=-3 e=10000 s=20 R3000 M120:580:000:0: c=128047 384143863 T=2.91 97
sqsort d=-3 e=10000 s=20 R3000 M120:009:018:0: c=141452 424357003 T=3.09 103
timsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=120392 361177167 T=10.73 358
my_qsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=136748 410244182 T=3.62 121
qsort20 d=-3 e=10000 s=80 R3000 M120:580:000:0: c=128047 384143863 T=3.20 107
sqsort d=-3 e=10000 s=80 R3000 M120:009:018:0: c=141420 424261003 T=3.36 112
timsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=120392 361177167 T=13.98 466
my_qsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=136776 82066150 T=3.52 586
qsort20 d=-3 e=10000 s=1000 R600 M120:580:000:0: c=128099 76859601 T=1.81 302
sqsort d=-3 e=10000 s=1000 R600 M120:009:018:0: c=141426 84856124 T=1.70 284
timsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=120391 72234833 T=12.81 2135