gapを広くとって並び替えてgapを1.3で割った値を新しいgapとするというわけだけど、1.3で割るってなんか計算の効率が悪そうな気がした。整数で計算するには『10倍してから13で割る』とか『100倍して130で割る』などとするけど、もう少し速くできそうな気がしたので試してみる
まず気になったのは『1.3で割る』というのは『何を掛ける』のと同じ結果になるのか。それで1を1.3で割るとだいたい0.769だということがわかる。そこで0.769を0.75にしても大して結果は変わらないだろうという根拠のない近似を行った。そして『0.75を掛ける』ことは『3倍してから4で割る』と同じになる。それで4で割るというのは右に2ビットシフトするというビット演算で実現できるので高速化ができると思いgapの間隔を縮める計算を書き直す。
修正前
gap = gap * 10 / 13;修正後
gap = (gap * 3) >> 2;
それで1,000,000個の整数のソートにかかった時間を何度か計ってみると
修正前:0.73〜0.75秒
修正後:0.675〜0.70秒
と若干高速化できた。ソートもしっかりできてるみたいだし、1.3で割る理由ってなんだったんだろう?1.3以外だと場合によってはソートできないとかあるのだろうか?それとも今回、たまたま1.3で割る場合より速かっただけで1.3で割る場合の方が速いことが多いとか?それとも、もっといい計算方法があるのだろうか?
どうでもいいけど人によってコムソートだったりコームソートだったりするけどどっちの方がいいんだろう?
10/13 もう一度計ったら、訂正前とほぼ同じ速さになりました…10月8日のときは20回以上やっても0.7秒よりかかることは無かったけど、なんだったんだろう…