サーチする

include?って，結局はサーチってことだ．実装がどうなってるかは知らないけれど．そんなことをシャワー浴びながら考えてたのだけれども，そういえばRubyでサーチアルゴリズムを書いたことが無いなぁと思い，書いてみることにしたのです．

まずは，サーチアルゴリズムをArrayに実装する．今回は簡単なリニアサーチとバイナリサーチだけですけど．

class Array
  def linear_search(item)
    each do |elem|
      return true if item == elem
    end
    return false
  end
  
  def binary_search(item)
    def search(item, array)
      middle = (array.size / 2).to_i
      return true if array[middle] == item
      return false if array.size == 0
      if array[middle] > item
        search(item, array[0,middle])
      else
        search(item, array[middle + 1, self.size])
      end
    end
    
    return search(item, self.sort)
  end
end

リニアサーチは，見るからにリニアサーチって感じがする．バイナリサーチってこんなんだっけ．あやふや．

実際にリニアサーチおよびバイナリサーチを使って，ベンチマークをとってみる．まずはリニアサーチから．

require 'search.rb'

max = 10000000
array = (1..max).to_a
p item = 3811999
p array.linear_search(item)

=>
$ time ruby l_search.rb 
3811999
true

real    0m12.735s
user    0m10.011s
sys     0m0.288s

3811999は，randで取ってきたもの．次に，バイナリサーチ．

require 'search.rb'

max = 10000000
array = (1..max).to_a
p item = 3811999 # もちろん，途中までは同じ．
p array.binary_search(item)

=>
$ time ruby b_search.rb 
3811999
true

real    0m7.596s
user    0m5.912s
sys     0m0.362s

若干早い．ちょっと嬉しい．

んじゃ，include?はどんだけ早いんだろう．

max = 10000000
array = (1..max).to_a
p item = 3811999 # もちろん，途中までは同じ．
p array.include?(item)

=>
$ time ruby include.rb 
3811999
true

real    0m7.655s
user    0m6.452s
sys     0m0.245s

んな無茶苦茶早いってことも無いのね．Cで実装してないのかしら．