Ruby方法的大O表示法？

Question

我怎样才能找到Ruby方法的复杂性？

例如长度？如果我查看源代码,我会看到:

               static VALUE
rb_ary_length(VALUE ary)
{
    long len = RARRAY_LEN(ary);
    return LONG2NUM(len);
}

但我不知道如何阅读,以找到大O符号.

Answer 1

没有维护Ruby方法的理论复杂性列表.您感兴趣的是minitest/benchmark,使用如下:

require 'minitest/autorun'
require 'minitest/benchmark'

class TestFoobar < Minitest::Benchmark
  def setup
    @foo_arrays = ( 1 .. 10_000 ).map { |n| [ 42 ] * n }
    # Because default benchmarking range is [1, 10, 100, 1_000, 10_000]
  end

  def bench_foo_size
    assert_performance_constant 0.99 do |n| @foo_arrays[ n ].size end
  end
end

如果运行上面的测试,您实际上可以看到Array#size方法的性能是不变的.如果您更改#bench_foo_size为:

def bench_foo_size
  assert_performance_linear 0.99 do |n| @foo_arrays[ n ].size end
end

测试实际上会失败,因为Array#size它不是线性的,而是次线性的.minitest/benchmark非常灵活,您可以将其应用于您自己的代码以及内置资产.

Answer 2

您无法从中获取相关信息。RARRAY_LEN你必须调查和的来源LONG2NUM。

估计方法复杂性的一个简单方法是使用沿您感兴趣的维度不同的参数运行基准测试，并将其绘制在图表上。