ユメのチカラ: 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