Module: BigO::ComplexityBase

Included in:
SpaceComplexity, TimeComplexity
Defined in:
lib/big-o/complexity_base.rb

Overview

ComplexityBase regroup every process common to the benchmarking of a function.

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#options ⇒ Hash

Returns Contains the different configurable options.

Returns:

  • (Hash) —

    Contains the different configurable options



15
16
17
 
# File 'lib/big-o/complexity_base.rb', line 15

def options
  @options
end

#result ⇒ Boolean

Returns Result from measurement.

Returns:

  • (Boolean) —

    Result from measurement



6
7
8
 
# File 'lib/big-o/complexity_base.rb', line 6

def result
  @result
end

#result_set ⇒ Hash

Returns Contains the whole benchmark.

Returns:

  • (Hash) —

    Contains the whole benchmark



9
10
11
 
# File 'lib/big-o/complexity_base.rb', line 9

def result_set
  @result_set
end

#scale ⇒ Float

Returns Element on which the whole benchmark is based (for n = 1).

Returns:

  • (Float) —

    Element on which the whole benchmark is based (for n = 1)



12
13
14
 
# File 'lib/big-o/complexity_base.rb', line 12

def scale
  @scale
end

Instance Method Details

#examine_result_set(real_complexity, expected_complexity) ⇒ Boolean

Parses data from #run_simulation.

examine_result_set will return true only if these conditions are met:

  • expected complexity is never exceeded. Some inconsistencies may however be allowed (see @options[:error_pct]).

  • there is a minimum of X results in real_complexity, where X is @options[:minimum_result_set_size]. if this condition is not met, an exception will be thrown.

Parameters:

  • real_complexity (Array)
  • expected_complexity (Array)

Returns:

  • (Boolean)

Raises:



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/big-o/complexity_base.rb', line 93

def examine_result_set(real_complexity, expected_complexity)
  if real_complexity.size <= @options[:minimum_result_set_size]
    raise SmallResultSetError.new(@options[:minimum_result_set_size])
  end

  allowed_inconsistencies = (expected_complexity.size * @options[:error_pct]).floor
  expected_complexity.each do |n, level|
    next if n == 1
    estimated_complexity  = @scale * level
    estimated_complexity += estimated_complexity * @options[:approximation]
    if estimated_complexity <= real_complexity[n]
      if allowed_inconsistencies > 0
        allowed_inconsistencies -= 1
        next
      end
      @result = false
      break
    end
  end

  @result = true if @result.nil?
  @result
end

#get_scale ⇒ Float

Finds what is the first measure of our function.

Returns:

  • (Float) 


120
121
122
123
124
125
126
 
# File 'lib/big-o/complexity_base.rb', line 120

def get_scale
  runs = []
  10.times do
    runs << measure(1, &@options[:fn])
  end
  runs.inject(:+) / 10
end

#initialize(options = {}) ⇒ void

Configures default values.

{
   :fn => lambda { |n| do_something(n) }  # function which will be measured [required]
   :level => lambda { |n| n }             # complexity of the function [required]
   :range => 1..20,                       # values of `n` for which it will run the function
   :timeout => 10,                        # time (in seconds) after which the simulation will stop running
   :approximation => 0.05,                # percentage by which we approximate our expected results
   :error_pct => 0.05,                    # percentage of times where we allow errors due to concurrent processing
   :minimum_result_set_size => 3          # minimum number of results we need to have consistent data
 }

Parameters:

  • options (Hash) (defaults to: {}) —

    the options necessary to benchmark the given lambda. Any of these options can be defined just before running a simulation using options.



32
33
34
35
36
37
38
39
40
 
# File 'lib/big-o/complexity_base.rb', line 32

def initialize(options = {})
  @options = { :range => 1..20,
               :timeout => 10,
               :approximation => 0.05,
               :error_pct => 0.05,
               :minimum_result_set_size => 3 }

  @options.merge!(options)
end

#process ⇒ Boolean

Benchmarks the given function (@fn) and tells if it follows the given pattern (@options[:level]).

Returns:

  • (Boolean) 


46
47
48
49
 
# File 'lib/big-o/complexity_base.rb', line 46

def process
  @scale ||= get_scale
  examine_result_set(*run_simulation)
end

#run_simulation ⇒ Array

Runs simulation.

A simulation can fail to execute every element in range because it exceeded the timeout limit. If no result was returned in the ‘timeout` time frame, this method will generate an exception.

Returns:

  • (Array) —

    contains an array (first element) of values which are the measurement of the function and another array (second element) of values which are the expected values for the first one.

Raises:

  • (Timeout::Error) 


59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/big-o/complexity_base.rb', line 59

def run_simulation
  real_complexity     = {}
  expected_complexity = {}

  begin
    Timeout::timeout(@options[:timeout]) do
      @options[:range].each do |n|
        next if (indicator = measure(n, &@options[:fn])) == 0
        real_complexity[n]     = indicator
        expected_complexity[n] = @options[:level].call(n)
      end
    end
  rescue Timeout::Error => e
    if real_complexity.empty? || expected_complexity.empty?
      raise e
    end
  end

  @result_set = real_complexity
  [real_complexity, expected_complexity]
end