●●●timsort よりも 高速 でかつ 安定・安全 な qsort ＝ sqsort (言語Cで記述)●●● ●sqsortの特徴は、同じキー値(県名・男女など)が現れる場合に極めて高速なことです。 ●また、qsortの改良版なのに、安定性があることです。 以下では、 「安定」とは、「キー値が同じ要素は、ソート前の順序をソート後も維持する」こととします。 「安全」とは、「悪意のある配列により、異常に長いソート時間を発生させることが不可能」 　　　　　　　なこととします。 sqsort では「安全」を実現するために、 clock()関数を再現性のない乱数として使用し、ピボットの候補を決定します。 これにより、理論上の最悪計算時間 O(n^2) は変化しませんが、 「悪意のある配列を作ることは不可能」となります。 sqsortは大雑把にいうと、対象配列(ptr)と補助配列(ptr2)で 次のような移動(Ａ,Ｂ)を繰り返します。 ptr2:............... → ptr2:332223....77787 → ptr2:332223....77787 ptr :357358257257237 Ａ ptr :5555........... Ｂ ptr :......5555..... sqsort・timsort の ソースコード・ベンチマークプログラム は 　　　　http://ww51.tiki.ne.jp/~srr-cake/qsort/ssc18/ 　　にあります。 sqsort(約350行 .oファイル約12800byte) は、 timsort(約1300行 .oファイル約31400byte) よりかなりコンパクトです。 qsortを含めた３種類のソートを比較すると次の表のようになります。 | 　　　　 | timsort | sqsort　 | qsort 非安定 | |:---------|:-------:|:--------:|:------------:| | 速さ　　 | △ | ◎ | ◎ | | 作業領域 | △ | △ | ◎ | | 安定性　 | ○ | ○ | × | | 安全性　 | ◎ | ○ | × | | サイズ　 | × | ○ | ◎ | 処理時間を測定したもの(benchmark.txt)を以下に記載します。 48行目でmy_sortよりsqsortが少し遅くなっていますが、 これは、sqsortの「安定性」実現のために、余分な要素の移動が起きたためです。 ----------------- benchmark.txt begin -------------------- 　　キー:同値なし 要素:1万個　要素サイズ:8,20,80,1000byte my_qsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=136798 547192609 T=3.77 94 timsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=120390 481561920 T=5.38 134 sqsort d=-3 e=10000 s=8 R4000 M000:000:000:0: c=141438 565754586 T=3.27 82 my_qsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=136804 410413695 T=4.73 158 timsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=120390 361170762 T=10.73 358 sqsort d=-3 e=10000 s=20 R3000 M000:000:000:0: c=141434 424304000 T=3.08 103 my_qsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=136804 410413695 T=3.61 120 timsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=120390 361170762 T=13.92 464 sqsort d=-3 e=10000 s=80 R3000 M000:000:000:0: c=141416 424249151 T=3.36 112 my_qsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=136845 82107153 T=3.48 581 timsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=120389 72233808 T=12.56 2094 sqsort d=-3 e=10000 s=1000 R600 M000:000:000:0: c=141351 84810864 T=1.69 281 　キー種別:100種　要素:1万個　要素サイズ:8,20,80,1000byte my_qsort d=100 e=10000 s=8 R6000 M000:000:000:0: c=62893 377363710 T=2.42 40 timsort d=100 e=10000 s=8 R6000 M000:000:000:0: c=103239 619435932 T=7.33 122 sqsort d=100 e=10000 s=8 R6000 M000:000:000:0: c=62388 374330081 T=2.23 37 my_qsort d=100 e=10000 s=20 R3000 M000:000:000:0: c=62926 188780724 T=2.52 84 timsort d=100 e=10000 s=20 R3000 M000:000:000:0: c=103239 309719470 T=8.59 286 sqsort d=100 e=10000 s=20 R3000 M000:000:000:0: c=62402 187208373 T=1.74 58 my_qsort d=100 e=10000 s=80 R4000 M000:000:000:0: c=62922 251691334 T=2.40 60 timsort d=100 e=10000 s=80 R4000 M000:000:000:0: c=103240 412961519 T=15.39 385 sqsort d=100 e=10000 s=80 R4000 M000:000:000:0: c=62376 249505124 T=2.56 64 my_qsort d=100 e=10000 s=1000 R500 M000:000:000:0: c=62919 31459751 T=2.17 434 timsort d=100 e=10000 s=1000 R500 M000:000:000:0: c=103239 51619835 T=9.62 1925 sqsort d=100 e=10000 s=1000 R500 M000:000:000:0: c=62401 31200583 T=1.19 237 　　キー種別:2種　要素:1万個　要素サイズ:8,20,80,1000byte my_qsort d=2 e=10000 s=8 R12000 M000:000:000:0: c=15020 180242977 T=1.16 10 timsort d=2 e=10000 s=8 R12000 M000:000:000:0: c=45262 543150430 T=7.89 66 sqsort d=2 e=10000 s=8 R12000 M000:000:000:0: c=15014 180176778 T=1.00 8 my_qsort d=2 e=10000 s=20 R7000 M000:000:000:0: c=15020 105142708 T=2.20 31 timsort d=2 e=10000 s=20 R7000 M000:000:000:0: c=45263 316841085 T=8.08 115 sqsort d=2 e=10000 s=20 R7000 M000:000:000:0: c=15046 105326276 T=0.95 14 my_qsort d=2 e=10000 s=80 R6000 M000:000:000:0: c=15020 90123066 T=1.20 20 timsort d=2 e=10000 s=80 R6000 M000:000:000:0: c=45263 271579105 T=9.36 156 sqsort d=2 e=10000 s=80 R6000 M000:000:000:0: c=15015 90091994 T=1.72 29 my_qsort d=2 e=10000 s=1000 R400 M000:000:000:0: c=15021 6008462 T=0.97 242 timsort d=2 e=10000 s=1000 R400 M000:000:000:0: c=45265 18106265 T=3.95 988 sqsort d=2 e=10000 s=1000 R400 M000:000:000:0: c=15010 6004395 T=0.77 192 　 キー:同値なし　百〜百万要素　要素サイズ:200byte my_qsort d=-3 e=100 s=200 R200000 M000:000:000:0: c=644 128893028 T=1.67 1 timsort d=-3 e=100 s=200 R200000 M000:000:000:0: c=538 107623993 T=4.89 2 sqsort d=-3 e=100 s=200 R200000 M000:000:000:0: c=691 138210336 T=1.38 1 my_qsort d=-3 e=1000 s=200 R14000 M000:000:000:0: c=10064 140901071 T=1.67 12 timsort d=-3 e=1000 s=200 R14000 M000:000:000:0: c=8682 121560507 T=5.39 39 sqsort d=-3 e=1000 s=200 R14000 M000:000:000:0: c=10530 147423146 T=1.16 8 my_qsort d=-3 e=10000 s=200 R1000 M000:000:000:0: c=136826 136826241 T=1.59 159 timsort d=-3 e=10000 s=200 R1000 M000:000:000:0: c=120389 120389545 T=6.25 625 sqsort d=-3 e=10000 s=200 R1000 M000:000:000:0: c=141353 141353954 T=1.17 117 my_qsort d=-3 e=100000 s=200 R60 M000:000:000:0: c=1727630 103657844 T=1.50 2498 timsort d=-3 e=100000 s=200 R60 M000:000:000:0: c=1534821 92089290 T=5.00 8333 sqsort d=-3 e=100000 s=200 R60 M000:000:000:0: c=1777877 106672678 T=1.62 2708 my_qsort d=-3 e=1000000 s=200 R7 M000:000:000:0: c=20971928 146803502 T=2.14 30557 timsort d=-3 e=1000000 s=200 R7 M000:000:000:0: c=18640815 130485706 T=7.12 101786 sqsort d=-3 e=1000000 s=200 R7 M000:000:000:0: c=21374068 149618482 T=2.70 38629 ================= benchmark.txt end ==================== my_qsort：ベンチマークテスト実行の計算機上の C ライブラリの qsort timqsort：https://github.com/patperry/timsort/ の timsort sqsort　：今回公開した sqsort d=キー種類 e=要素数 s=要素サイズ R繰返し回数 c=比較回数/R T=処理秒数 各行の最後の数値がソート１回あたりの処理時間(10μ秒単位)です