Big-O
Big-O is a gem which analyse an anonymous function and verify that it follow a specific pattern in its memory usage or its execution time.
Requirements
Calculation of memory space is done via ps
, and therefore, doesn't work on Windows.
This gem has been tested on Mac OS X, using Ruby 1.9.3.
Install
Installation is made through RubyGem:
gem install big-o
Usage
Directly in your code
Checking if a function has a complexity of O(n) is as simple as this:
require 'big-o'
time_complexity = BigO::TimeComplexity({
:fn => lambda { |n| do_something_time_consuming(n) },
:level => lambda { |n| n }
})
time_complexity.process # => true if it is growing in time constantly.
It is also possible to define multiple configuration parameters:
require 'big-o'
space_complexity = BigO::SpaceComplexity({
:fn => lambda { |n| do_something_space_consuming(n) }
:level => lambda { |n| n },
:range => 1..20, # value of n
:timeout => 10, # time in seconds
:approximation => 0.05, # percentage
:error_pct => 0.05, # percentage
:minimum_result_set_size => 3 # minimum results
})
RSpec Matchers
If you are using RSpec, there is a matcher already defined for matching a complexity level:
require 'big-o'
require 'big-o-matchers'
describe 'do_something_time_consuming' do
before :each do
@time_complexity = BigO::TimeComplexity({
:fn => lambda { |n| do_something_time_consuming(n) }
})
end
it 'should have a complexity of O(n)' do
@time_complexity.should match_complexity_level 'O(n)', lambda { |n| n }
end
it 'should not have a complexity of O(1)' do
@time_complexity.should match_complexity_level 'O(1)', lambda { |_| 1 }
end
end
The string used as the first parameter (e.g. 'O(n)'
) is used to describe the lambda given as the
second parameter.
Reference
You may want to read more on the subject by reading:
License
Complexity is licensed under the MIT License - see the LICENSE file for details