Ruby方法的大O表示法？

我怎样才能找到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的来源。

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

Answer 3

length方法只是O(1) 。 数组的长度存储在变量中，无需进一步计算即可返回。

怎么找出来？ 通过阅读源代码并分析实现和算法。