Ruby Array#assoc 是否使用线性搜索？

Question

嗯..还不能读这个..但是 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;
}

Answer 1

就个人而言，我觉得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

所以，是的，它很容易地看到，这确实是不使用线性搜索。

但是您实际上并不需要查看源代码来弄清楚这一点。还能是什么？与搜索树或排序数组不同，没有可以利用的结构或顺序来加速它。