1

うーん..まだこれを読むことはできません..しかし、Ruby Array＃assocは線形検索を使用していますか？

rb_ary_assoc(VALUE ary, VALUE key)
{
    long i;
    VALUE v;

    for (i = 0; i < RARRAY_LEN(ary); ++i) {
        v = rb_check_array_type(RARRAY_PTR(ary)[i]);
        if (!NIL_P(v) && RARRAY_LEN(v) > 0 &&
            rb_equal(RARRAY_PTR(v)[0], key))
            return v;
    }
    return Qnil;
}
4

2 に答える 2

5

個人的には、RubiniusのソースコードはYARVのソースコードよりもはるかに読みやすいと思います。（実際、他のすべてのRuby実装のソースコードはYARVやMRIよりも読みやすいと思います。）

これはRubiniusからの実装ですArray#assoc：

def assoc(obj)
  each do |x|
    if x.kind_of? Array and x.first == obj
      return x
    end
  end

  nil
end

したがって、はい、それが実際に線形探索を使用していることは簡単にわかります。

しかし、それを理解するためにソースコードを実際に見る必要はありません。他に何ができるでしょうか？検索ツリーや並べ替えられた配列とは異なり、高速化するために利用できる構造や順序はありません。

于 2013-01-23T15:53:23.260 に答える
4

はい; 配列を反復処理します。RARRAY_PTR(ary)[i]

配列がソートされている場合とされていない場合があることを考えると、これが理にかなっている唯一のことです。

（Ruby 2ではが導入されることに注意してください。bsearch速度が気になる場合は、バイナリ検索用に少なくとも2〜3個のgemがあります。詳細についてはhttps://stackoverflow.com/a/8672512/438992を参照してください。）

于 2013-01-23T15:33:35.333 に答える