#includes:（あるいは Ruby の include?）のコストは高く付く

ユメのチカラ: Rubyで習作の性能評価 より。正直、あまりコストのことは考えていなかったのですが、こんなふうに歴然とした差を見せつけられると、簡潔に書けて便利だからといって、安易に #includes: を使ってはいけないのだな…と気づかされます。勉強になりました。

手元の環境でも、36 万強の要素数の場合に、先頭、中央、末尾にある要素の存在確認をするのにかかる時間を計測してみました。要素には、重複しない大量のデータということで、与えた文字列の順列を生成し、これを配列の要素や辞書（ハッシュ）のキーとして用いています。

Squeak Samlltalk

| str n colletion array dictionary keys |

str := 'abcdefghi'. n := 100.

colletion := OrderedCollection new.
str permutationsDo: [:each | colletion add: each asSymbol].

array := colletion asArray.
dictionary := Dictionary new.
colletion do: [:key | dictionary at: key put: nil].

keys := {array first. array middle. array last}.

^ {#size -> array size.
    #(first middle last) with: keys collect: [:pos :key |
        pos -> {
            #arry -> ([n timesRepeat: [array includes: key]] timeToRun / 1.0e3).
            #hash -> ([n timesRepeat: [dictionary at: key]] timeToRun / 1.0e3)}]}

結果

{#size->362880 .
  {#first->{#arry->0.117 . #hash->0.0} .
   #middle->{#arry->13.828 . #hash->0.001} .
   #last->{#arry->27.767 . #hash->0.0}}}

同じことを Ruby でも…と思ったのですが、残念ながら Ruby には、文字列の順列を生成するためのサービスが標準では提供されていません。そこで、Squeak Smalltalk のものを String に permutations_each（本体は perm_start_at）として定義しました。

Ruby (include.rb)

class String
  def permutations_each(&b); dup.perm_start_at(0,&b) end
  def perm_start_at(i,&b)
    return self if i > size-1
    return b.call(self) if i == size-1
    for j in i..size-1
      swap(i,j); perm_start_at(i+1,&b); swap(i,j)
    end
  end
  def swap(i,j); self[i],self[j]=self[j],self[i] end
end

class Proc
  def time_to_run; t=Time.now; self.call; Time.now-t end
end


a = []; ARGV[0].permutations_each{ |e| a << e.to_sym }
h = {}; a.each{ |k| h[k] = nil }
n = ARGV[1].to_i

print "size->#{a.size}\n"
["first", "middle", "last"].zip([a[0], a[a.size/2], a[-1]]).each do |pos,key|
  print "#{pos}\n"
  print "  arry->#{proc{n.times{a.include?(key)}}.time_to_run}\n"
  print "  hash->#{proc{n.times{h[key]}}.time_to_run}\n"
end

結果

$ ruby include.rb abcdefghi 100
size->362880
first
  arry->0.00021
  hash->0.000218
middle
  arry->10.478766
  hash->0.000545
last
  arry->21.427794
  hash->0.000235