Clever Geek Handbook

Big O remark for Ruby methods?

How can I find the complexity of a Ruby method?

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

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

But I don't know how to read it to find Big O notation.

+3


source to share


3 answers


There is no list of the theoretical complexities of Ruby methods. You are interested in 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

If you do the above test, you can see that the performance of the method is Array#size

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

The test will indeed fail because it is Array#size

not linear but sublinear. minitest/benchmark

is flexible and you can apply it to your own code as well as embedded resources.

+4


source


You cannot get the relevant information. You must research the source RARRAY_LEN

and LONG2NUM

.



An easy way to estimate the complexity of a method is to run tests with arguments that vary in size of interest, and plot it on a graph.

+2


source


It's easy O(1)

for the method length

. The length of the array is stored in a variable and can be returned without further calculations.

How to find out? Reading the source code and analyzing the implementation and algorithms.

+1


source






More articles:


All Articles