ククログ

株式会社クリアコード > ククログ > Ruby 1.9.xでRange#include?を高速に動かす方法

Ruby 1.9.xでRange#include?を高速に動かす方法

Ruby 1.9.xではRange#include?の実装が変わり、Ruby 1.8.xよりも圧倒的に遅くなるケースがあります。これは、Ruby 1.9.xへ移行したときの有名なハマりポイントの1つでしょう。

例えば、こんなケースです。

require 'time'
require 'benchmark'

Benchmark.bm(10) do |bm|
  march = Time.parse("2010/03/01")...Time.parse("2010/04/01")
  march_15 = Time.parse("2010/03/15")
  bm.report("include?") do
    march.include?(march_15)
  end
end

2010年3月15日が2010年3月に入っているかを調べています。

これをRuby 1.8.7で動かすとこうなります。

% ruby -v /tmp/range-include.rb
ruby 1.8.7 (2010-01-10 patchlevel 249) [x86_64-linux]
                user     system      total        real
include?    0.000000   0.000000   0.000000 (  0.000011)

一瞬ですね。

Ruby 1.9.1で動かすとこうなります。

% ruby1.9.1 -v /tmp/range-include.rb
ruby 1.9.1p378 (2010-01-10 revision 26273) [x86_64-linux]
                user     system      total        real
include?    1.360000   0.030000   1.390000 (  1.766556)

1万倍以上も遅くなります。

原因

どうしてこうなるのかというと、1.8.xのRange#include?と1.9.xのRange#include?では引数の値の見つけ方が異なるからです。

1.8.xでは引数が範囲の最初の値より大きいかつ最後の値より小さい、ことだけを確認していました。1.9.xでは範囲の最初から最後まで順に繰り返し、その中に引数と==な値が含まれるかどうかを確認します。コードで表すとこんな感じです。

def range_include_18(range, value)
  range.begin < value and value < range.end
end

def range_include_19(range, value)
  range_value = range.begin
  loop do
    return true if range_value == value
    range_value = range_value.succ
    break if range_value >= range.end
  end
  false
end

Time#succは1秒先の時間を返します。そのため、一回のRange#include?で最大2678400回ループをまわすことになります(範囲に入っていないとき、つまり、falseを返すとき)。

(Time.parse("2010/03/01")...Time.parse("2010/04/01")).to_a.size # => 2678400

真ん中あたりのTime.parse("2010/03/15")でも1209601番目なので、1.8.xのRange#include?と比べてだいぶ遅くなるというわけです。

(Time.parse("2010/03/01")..Time.parse("2010/03/15")).to_a.size # => 1209601

解決法

1.9.xには1.8.xのRange#include?と同じように比較するメソッドRange#cover?が追加されているのでそれを使うとよいでしょう。

require 'time'
require 'benchmark'

Benchmark.bm(10) do |bm|
  march = Time.parse("2010/03/01")...Time.parse("2010/04/01")
  march_15 = Time.parse("2010/04/01")
  bm.report("cover?") do
    march.cover?(march_15)
  end
end

実行するとたしかに速いです。

% ruby1.9.1 -v /tmp/range-cover.rb
ruby 1.9.1p378 (2010-01-10 revision 26273) [x86_64-linux]
                user     system      total        real
cover?      0.000000   0.000000   0.000000 (  0.000010)

ただし、1.8.xにはRange#cover?はないので、Range#cover?を使うと1.9.x専用のスクリプトになってしまいます。

高速なRange#include?

実は、1.9.xのRange#include?も、数字の範囲または文字の範囲、の場合は高速に動作します。この場合だけ特別扱いされていて1.8.xと同様の比較方法を用いているからです。つまり、どうにかして数字の範囲か文字の範囲に落としこめば1.8.xでも1.9.xでも高速に動作するようなスクリプトを書けるということです。

Timeの場合はTime#to_iで数値にしてしまうのがよいでしょう。

require 'time'
require 'benchmark'

Benchmark.bm(10) do |bm|
  march = Time.parse("2010/03/01")...Time.parse("2010/04/01")
  march_15 = Time.parse("2010/03/15")
  bm.report("Time") do
    march.include?(march_15)
  end

  march_integer = (Time.parse("2010/03/01").to_i)...(Time.parse("2010/04/01").to_i)
  march_15_integer = Time.parse("2010/03/15").to_i
  bm.report("Integer") do
    march_integer.include?(march_15_integer)
  end
end

結果は一目瞭然です。

% ruby1.9.1 -v /tmp/range-include-integer.rb
ruby 1.9.1p378 (2010-01-10 revision 26273) [x86_64-linux]
                user     system      total        real
Time        1.230000   0.030000   1.260000 (  1.504888)
Integer     0.000000   0.000000   0.000000 (  0.000009)

まとめ

徐々にRuby 1.9.xを使う人が増えているかもしれない、ということで、Ruby 1.9.xを使った場合にハマりそうなポイントとその解決法を紹介しました。1.9.xでは変わったことがたくさんあります。1.9.xのことをもっと知って上手に付き合ってみてはいかがでしょうか。