Array＃にはどのアルゴリズムが含まれていますか？使用？

xが配列の場合、x.include?(y)はyがxにあるかどうかを確認しますか？アルゴリズムは何ですか？Array＃にはどのアルゴリズムが含まれていますか？使用？

出典

2012-01-27 locoboy

関数のソースはhttp://ruby-doc.org/core-1.9.3/Array.html#method-i-include-3F – oldergod

です。これは 'O（n）'です。 'O（1）'では、代わりに 'Set'を使います。 –

配列をソートする必要がないので、アルゴリズムは「各要素を見て、それが一致するかどうか」より優れたものにはなりません。グレッグHewgillの答えに加えとして

出典

2012-01-27 01:19:52

Gotchaなので、並べ替えられた配列を持っていれば、何か他のものを使うことができます。 – locoboy

@ cfarm54大きなソート配列では、ほとんどの場合、バイナリ検索が高速になります。 http：///xcc.net/ruby-bsearch/index.html.en –

うん、これはルビーのための機能がないと仮定します。 – locoboy

、この方法のためのRuby 1.9.3からのソースコードである：グレッグが言ったように

VALUE 
rb_ary_includes(VALUE ary, VALUE item) 
{ 
    long i; 

    for (i=0; i<RARRAY_LEN(ary); i++) { 
     if (rb_equal(RARRAY_PTR(ary)[i], item)) { 
      return Qtrue; 
     } 
    } 
    return Qfalse; 
}

したがって、アルゴリズムは、アレイを通るだけ線形探索です。

出典

2012-01-27 01:24:03 blahman

+1ルーク、ソースを使用します。 –

Array＃にはどのアルゴリズムが含まれていますか？使用？

答えて

関連する問題