Rubyの数値比較について

背景

最近仕事でrubyを使うようになり、ついでならと思いAtCoderも始めてみました。
C問題をやったときに、数値比較の処理を書き換えたらめちゃくちゃ早くなったという話。

どういった処理をしたかったのか

計算自体はシンプルで、特定の値が最小値と最大値の間に含まれているかを判定したかった。

ruby

k = 100
min = 0
max = arr.length - 1

# arrのキーの範囲外を指定しないようにする
if k >= min && k <= max
    puts arr[k]
end

ここの k >= min && k <= max をどう書くのかという話。

結論

早い順で並べると

比較演算子(>=, <=)で判定：一番早い

ruby

k >= min k <= max

intのbetween?関数を使う

ruby

if k.between?(0, max)

※betweenの引数両方を含むので注意
https://docs.ruby-lang.org/ja/latest/method/Comparable/i/between=3f.html

setのinclude?を使う:一番遅い

ruby

if (0..max).include?(k)

検証

以下のコードを実行し、処理時間を比較

ruby

times = 10**8

max = 100000

cnt = 0
start_time = Time.now
times.times do
  v = rand((max * 2.1).to_i) - (max*0.1).to_i
  if v >= 0 && v <= max
    cnt += 1
  end
end

p cnt
p "#{Time.now - start_time} sec"

cnt = 0
start_time = Time.now
times.times do
  v = rand((max * 2.1).to_i) - (max*0.1).to_i
  if v.between?(0, max)
    cnt += 1
  end
end

p cnt
p "#{Time.now - start_time} sec"


cnt = 0
start_time = Time.now
times.times do
  v = rand((max * 2.1).to_i) - (max*0.1).to_i
  if (0..max).include?(v)
    cnt += 1
  end
end

p cnt
p "#{Time.now - start_time} sec"

結果は以下の通り

47620057
"14.872639993 sec"
47616640
"16.715346883 sec"
47621783
"20.541049745 sec"

最小値、最大値の幅を狭めてみてもあまり結果は変わらず。
単純に数値が一定の範囲内に収まっているかどうかは、比較演算子を使うのが一番高速に動くみたい。

余談

AtCoderでinclude?を使って提出していたところ、2200msでTLEを食らったが、比較演算子に書き直したところ1300msになりました。
結構ループや再帰処理をしたので、こんなに変わるとは・・・、