Ruby 方法的大 O 符号? [英] Big O notation for Ruby methods?

问题描述

如何找出 Ruby 方法的复杂性?

How can I find the complexity of a Ruby method?

例如长度?如果我查看源代码，我会看到:

For example length? If I look at the source code, I see this:

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

但我不知道如何阅读它才能找到大 O 符号.

But I don't know how to read that in order to find the Big O notation.

推荐答案

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

There is no maintained list of theoretical complexities of Ruby methods. Of interest to you is minitest/benchmark, which is used like this:

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 更改为:

If you run the above test, you can actually see that the performance of Array#size method is constant. If you change #bench_foo_size to:

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

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

The test will actually fail, because Array#size is not linear, but sublinear. minitest/benchmark is flexible and you can apply it to your own code as well as to built-in assets.

这篇关于Ruby 方法的大 O 符号?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！