Range#include?の落とし穴（遅い）

# 結論
`Range` オブジェクトの要素が多く且つ数値では無い場合、 `Range#include?` ではなく **`Range#cover?`** または **`Comparable#between?`** を使うべき。

# `Range#include?`
ある値が範囲内にあるかどうか判断する際に `Range#include?` を使うことが良くあると思います。この `Range#include?` のエイリアスには `Range#===` があり、 case 文での判断にも用いられています。 Ruby では主要なメソッドであるとも言えるでしょう。
>## instance method `Range#===`
- `self === obj` -> `bool`
- `include?(obj)` -> `bool`
- `member?(obj)` -> `bool`

>`obj` が範囲内に含まれている時に真を返します。
`Range#===` は主に case 式での比較に用いられます。
`<=>` メソッドによる演算により範囲内かどうかを判定するには `Range#cover?` を使用してください。
[instance method Range#===](http://rurema.clear-code.com/2.2.0/method/Range/i/=3d=3d=3d.html)

# `Range#cover?`
類似のメソッドに `Range#cover?` があります。先ほどの引用にもありましたが `<=>` メソッドにより範囲内かどうかを判定します。

>## instance method `Range#cover?`
- `cover?(obj)` -> `bool`

>`obj` が範囲内に含まれている時に真を返します。
`Range#include?` と異なり `<=>` メソッドによる演算により範囲内かどうかを判定します。 `Range#include?` は原則として離散値を扱い、 `Range#cover?` は連続値を扱います。 （数値については、例外として `Range#include?` も連続的に扱います。）
[instance method Range#cover?](http://rurema.clear-code.com/2.2.0/method/Range/i/cover=3f.html)

違いをやはりマニュアルから引用します。
>```rb
# String の例
('b'..'d').include?('d')    # => true
('b'..'d').include?('ba')   # => false
('b'..'d').cover?('d')      # => true
('b'..'d').cover?('ba')     # => true
```

というのは 

```rb
("b".."d").to_a #=> ["b", "c", "d"]
```
なので `"ba"` は含まれていない。よって `Range#include?` では `false` になる。
そして一方、

```rb
"b" < "ba" #=> true
"ba" < "d" #=> true
```
だから `Range#cover?` では `true` になるわけです。
#仕様変更は Ruby 1.9 から
るびきちさんの名著 [Ruby逆引きハンドブック](http://www.c-r.com/book/detail/705) p.426 によると

> 「`Range#include?`」は、Ruby 1.9で仕様が変更されました。Ruby 1.8までは単に大小比較で判別していましたが、Ruby 1.9では数値、1文字の文字列以外は「`Enumerable#include?`」が呼び出されてコレクションに含まれているかどうかを判別するようになりました。そのため、**2文字以上の文字列による範囲オブジェクトに対して「`Range#include?`」を呼び出すと、非常に遅くなります**（引用者強調）。Ruby 1.8のように大小比較で判別するならば「`Comparable#between?`」か新設された「`Range#cover?`」を使用します。

としてベンチマークが示されています。

```rb
("air".."fairy").count #=> 2765082

require 'benchmark'
Benchmark.bm(20) do |b|
  b.report("between?") { 100.times { "elf".between?("air", "fairy") } }
  b.report("cover?")   { 100.times { ("air".."fairy").cover?("elf") } }
  b.report("include?") { 100.times { ("air".."fairy").include?("elf") } }
  b.report("case")     { 100.times { case "elf" when "air".."fairy" then 1 end } }
end
```
（オリジナルから若干並び替えました）
`include?` メソッドだと2765082個と逐一比較しているため遅くなる、ということでしょう。 `case` 文でも同様です。

このベンチマークをRuby 各バージョンで改めて実行して、結果を確認してみます。繰り返し回数は1000回に増やします。

# Ruby 1.8.7
```irb
$ rbenv global 1.8.7-p375 
$ irb
irb(main):001:0> ("air".."fairy").count
=> 2765082
irb(main):002:0> 
irb(main):003:0* require 'benchmark'
=> true
irb(main):004:0> Benchmark.bm(20) do |b|
irb(main):005:1*   b.report("between?") { 1000.times { "elf".between?("air", "fairy") } }
irb(main):006:1> # b.report("cover?")   { 1000.times { ("air".."fairy").cover?("elf") } }
irb(main):007:1*   b.report("include?") { 1000.times { ("air".."fairy").include?("elf") } }
irb(main):008:1>   b.report("case")     { 1000.times { case "elf" when "air".."fairy" then 1 end } }
irb(main):009:1> end
                          user     system      total        real
between?              0.000000   0.000000   0.000000 (  0.001401)
include?              0.000000   0.000000   0.000000 (  0.000870)
case                  0.010000   0.000000   0.010000 (  0.002106)
```
`include?` メソッドでも `between?` メソッドと同じく速いです。

# Ruby 1.9.3
```rb
$ rbenv global 1.9.3-p551 
$ pry
[1] pry(main)> ("air".."fairy").count
=> 2765082
[2] pry(main)> 
[3] pry(main)> require 'benchmark'
=> true
[4] pry(main)> Benchmark.bm(20) do |b|
[4] pry(main)*   b.report("between?") { 1000.times { "elf".between?("air", "fairy") } }  
[4] pry(main)*   b.report("cover?")   { 1000.times { ("air".."fairy").cover?("elf") } }  
[4] pry(main)*   b.report("include?") { 1000.times { ("air".."fairy").include?("elf") } }  
[4] pry(main)*   b.report("case")     { 1000.times { case "elf" when "air".."fairy" then 1 end } }  
[4] pry(main)* end  
                           user     system      total        real
between?               0.000000   0.000000   0.000000 (  0.000406)
cover?                 0.000000   0.000000   0.000000 (  0.000592)
include?               1.100000   0.010000   1.110000 (  1.102654)
case                   1.110000   0.000000   1.110000 (  1.111640)
```
`include?` メソッドが遅くなりました。
以下、 Ruby 2.2.1まで同様でした。

# Ruby 2.0.0
```rb
$ rbenv global 2.0.0-p576 
$ pry
[1] pry(main)> ("air".."fairy").count
=> 2765082
[2] pry(main)> 
[3] pry(main)> require 'benchmark'
=> true
[4] pry(main)> Benchmark.bm(20) do |b|
[4] pry(main)*   b.report("between?") { 1000.times { "elf".between?("air", "fairy") } }  
[4] pry(main)*   b.report("cover?")   { 1000.times { ("air".."fairy").cover?("elf") } }  
[4] pry(main)*   b.report("include?") { 1000.times { ("air".."fairy").include?("elf") } }  
[4] pry(main)*   b.report("case")     { 1000.times { case "elf" when "air".."fairy" then 1 end } }  
[4] pry(main)* end  
                           user     system      total        real
between?               0.000000   0.000000   0.000000 (  0.000433)
cover?                 0.000000   0.000000   0.000000 (  0.000609)
include?               0.900000   0.000000   0.900000 (  0.902766)
case                   0.890000   0.010000   0.900000 (  0.891280)
```

# Ruby 2.1
```rb
$ rbenv global 2.1.5 
$ pry
[1] pry(main)> ("air".."fairy").count
=> 2765082
[2] pry(main)> 
[3] pry(main)> require 'benchmark'
=> true
[4] pry(main)> Benchmark.bm(20) do |b|
[4] pry(main)*   b.report("between?") { 1000.times { "elf".between?("air", "fairy") } }  
[4] pry(main)*   b.report("cover?")   { 1000.times { ("air".."fairy").cover?("elf") } }  
[4] pry(main)*   b.report("include?") { 1000.times { ("air".."fairy").include?("elf") } }  
[4] pry(main)*   b.report("case")     { 1000.times { case "elf" when "air".."fairy" then 1 end } }  
[4] pry(main)* end  
                           user     system      total        real
between?               0.000000   0.000000   0.000000 (  0.000986)
cover?                 0.010000   0.000000   0.010000 (  0.001412)
include?               0.770000   0.000000   0.770000 (  0.781633)
case                   0.810000   0.000000   0.810000 (  0.814503)
```
# Ruby 2.2
```rb
$ rbenv global 2.2.1 
$ pry
[1] pry(main)> ("air".."fairy").count
=> 2765082
[2] pry(main)> 
[3] pry(main)> require 'benchmark'
=> true
[4] pry(main)> Benchmark.bm(20) do |b|
[4] pry(main)*   b.report("between?") { 1000.times { "elf".between?("air", "fairy") } }  
[4] pry(main)*   b.report("cover?")   { 1000.times { ("air".."fairy").cover?("elf") } }  
[4] pry(main)*   b.report("include?") { 1000.times { ("air".."fairy").include?("elf") } }  
[4] pry(main)*   b.report("case")     { 1000.times { case "elf" when "air".."fairy" then 1 end } }  
[4] pry(main)* end  
                           user     system      total        real
between?               0.000000   0.000000   0.000000 (  0.000768)
cover?                 0.000000   0.000000   0.000000 (  0.000729)
include?               0.870000   0.000000   0.870000 (  0.883959)
case                   0.790000   0.010000   0.800000 (  0.791134)
```

#参考
- [Ruby 1.9.xでRange#include?を高速に動かす方法 - ククログ(2010-03-25)](http://www.clear-code.com/blog/2010/3/25.html)
- [[ruby-dev:37052] Re: [Bug #736] Range#include? が遅い](http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-dev/37052)