Array#include?の速度
rubyを書いているとよくArray#include? を使う事が多いのですが、これのパフォーマンスが気になったの調査して見ました。
パフォーマンスの調査としては最悪のケースを考えたいので、要素が引っかからない場合(線形探索と仮定した場合、Arrayのすべての要素を舐める必要がある)を対象とします。
def make_array_number_of(n) array = [] n.times do |i| array << "hoge#{i}" end array end def include_performance(array) a=Time.now pp array.include?("gaga") b=Time.now pp b-a end [1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000].each do |n| pp "#{n}s array" make_array_number_of(n).tap do |array| include_performance(array) end end
結果
someone $ ruby performance.rb "1s array" false 2.7e-05 "10s array" false 3.1e-05 "100s array" false 3.7e-05 "1000s array" false 9.3e-05 "10000s array" false 0.000857 "100000s array" false 0.001764 "1000000s array" false 0.016368 "10000000s array" false 0.167093 "100000000s array" false 1.78809
要素が増えると線形的に探索時間が増加している(要素が10倍になると、探索時間も10倍)になるように見えます。
つまりArrayに対する include? はArrayの要素が増えて来ると、それだけボトルネックになるようです。
ちなみにHashを使うと、要素に対してO(1)でアクセスする事が出来るようになります。
def make_array_number_of(n) array = [] n.times do |i| array << "hoge#{i}" end array end def include_performance(array) a=Time.now pp array.include?("gaga") b=Time.now pp b-a end def make_hash_number_of(n) hash = {} n.times do |i| hash["hoge#{i}"] = true end hash end def hash_performance(hash) a=Time.now pp hash.include?("gaga") b=Time.now pp b-a end [1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000].each do |n| pp "#{n}s array" make_array_number_of(n).tap do |array| include_performance(array) end make_hash_number_of(n).tap do |hash| hash_performance(hash) end end
結果
someone $ ruby performance.rb "1s array" false 2.7e-05 false 2.1e-05 "10s array" false 3.1e-05 false 2.9e-05 "100s array" false 6.6e-05 false 3.6e-05 "1000s array" false 6.8e-05 false 0.000114 "10000s array" false 0.000376 false 9.1e-05 "100000s array" false 0.006702 false 7.7e-05 "1000000s array" false 0.01912 false 0.000101 "10000000s array" false 0.171654 false 7.1e-05 "100000000s array" false 1.888531 false 0.000158
こちらについてはHashの要素数がどれだけ増えても、探索時間に変化はありませんでした。 つまり配列の要素にするよりはハッシュのキーにした方が早くアクセス出来るということになります。
おまけ
Cのソースを見てみると、同じ include? でもかなり実装に差異があることが分かります。
Array
/* * call-seq: * ary.include?(object) -> true or false * * Returns +true+ if the given +object+ is present in +self+ (that is, if any * element <code>==</code> +object+), otherwise returns +false+. * * a = [ "a", "b", "c" ] * a.include?("b") #=> true * a.include?("z") #=> false */ VALUE rb_ary_includes(VALUE ary, VALUE item) { long i; VALUE e; for (i=0; i<RARRAY_LEN(ary); i++) { e = RARRAY_AREF(ary, i); if (rb_equal(e, item)) { return Qtrue; } } return Qfalse; }
Hash
/* * call-seq: * hsh.has_key?(key) -> true or false * hsh.include?(key) -> true or false * hsh.key?(key) -> true or false * hsh.member?(key) -> true or false * * Returns <code>true</code> if the given key is present in <i>hsh</i>. * * h = { "a" => 100, "b" => 200 } * h.has_key?("a") #=> true * h.has_key?("z") #=> false * * Note that <code>include?</code> and <code>member?</code> do not test member * equality using <code>==</code> as do other Enumerables. * * See also Enumerable#include? */ MJIT_FUNC_EXPORTED VALUE rb_hash_has_key(VALUE hash, VALUE key) { if (RHASH_AR_TABLE_P(hash) && ar_lookup(hash, key, 0)) { return Qtrue; } else if (RHASH_ST_TABLE_P(hash) && st_lookup(RHASH_ST_TABLE(hash), key, 0)) { return Qtrue; } return Qfalse; }
static int ar_lookup(VALUE hash, st_data_t key, st_data_t *value) { st_hash_t hash_value = do_hash(key); unsigned bin = find_entry(hash, hash_value, key); if (bin == RHASH_AR_TABLE_MAX_BOUND) { return 0; } else { HASH_ASSERT(bin < RHASH_AR_TABLE_MAX_BOUND); if (value != NULL) { *value = RHASH_AR_TABLE_REF(hash, bin)->record; } return 1; } }
static inline st_hash_t do_hash(st_data_t key) { st_hash_t hash = (st_hash_t)(*objhash.hash)(key); return (RESERVED_HASH_VAL == hash) ? RESERVED_HASH_SUBSTITUTION_VAL : hash; }
ハッシュの仕組みが分かっていないと難しいですね。(st_hash_t)(*objhash.hash)(key) はおそらく hash[key] の事でしょう。
正直これ以上追うのはしんどかったので追っていないのですが、仕組みとしては「Rubyソースコード完全解説」に記載されているシステム上で使用しているハッシュテーブルと同じ仕組みを使っているという認識です。
詳しくは下記のリンク先をご覧下さい。
