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 将引入 a bsearch，并且至少有 2-3 个 gem 用于二进制搜索，如果您关心速度。有关详细信息，请参阅https://stackoverflow.com/a/8672512/438992。）

于 2013-01-23T15:33:35.333 回答