Ruby

Range#include?の落とし穴(遅い)

More than 3 years have passed since last update.


結論

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#===



Range#cover?

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


instance method Range#cover?



  • cover?(obj) -> bool

obj が範囲内に含まれている時に真を返します。

Range#include? と異なり <=> メソッドによる演算により範囲内かどうかを判定します。 Range#include? は原則として離散値を扱い、 Range#cover? は連続値を扱います。 (数値については、例外として Range#include? も連続的に扱います。)

instance method Range#cover?


違いをやはりマニュアルから引用します。


# String の例

('b'..'d').include?('d') # => true
('b'..'d').include?('ba') # => false
('b'..'d').cover?('d') # => true
('b'..'d').cover?('ba') # => true

というのは

("b".."d").to_a #=> ["b", "c", "d"]

なので "ba" は含まれていない。よって Range#include? では false になる。

そして一方、

"b" < "ba" #=> true

"ba" < "d" #=> true

だから Range#cover? では true になるわけです。


仕様変更は Ruby 1.9 から

るびきちさんの名著 Ruby逆引きハンドブック 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?」を使用します。


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

("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

$ 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

$ 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

$ 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

$ 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

$ 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)


参考