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);
}
But I don't know how to read that in order to find the Big O notation.
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
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
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.
It is just O(1)
for the length
method. The length of an array is stored in a variable and can be returned without further calculations.
How to find out? By reading the source code and analysing the implementation and algorithms.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With