Class: ComplexityAssert::QuadraticComplexityModel

Inherits:
Object
  • Object
show all
Defined in:
lib/complexity_assert/quadratic_complexity_model.rb

Overview

Generates a sample of execution timings to run a linear regression in order to predict another execution time

Instance Method Summary collapse

Instance Method Details

#analyze(timings) ⇒ Object

timings : [[size,timing], …]



7
8
9
10
11
12
13
14
15
16
17
18
 
# File 'lib/complexity_assert/quadratic_complexity_model.rb', line 7

def analyze(timings)
  sqrt_timings = timings.map do |size, timing|
    [size, Math.sqrt(timing)]
  end
  linear_model = SimpleLinearRegression.new(*sqrt_timings.transpose)
  sqrt_slope = linear_model.slope
  sqrt_y_intercept = linear_model.y_intercept

  @quadratic = sqrt_slope * sqrt_slope
  @slope = 2* sqrt_slope * sqrt_y_intercept
  @y_intercept = sqrt_y_intercept * sqrt_y_intercept
end

#predict_run_time(input_data_size) ⇒ Object 



20
21
22
 
# File 'lib/complexity_assert/quadratic_complexity_model.rb', line 20

def predict_run_time(input_data_size)
  @y_intercept + @slope * input_data_size + @quadratic * input_data_size * input_data_size
end

#to_s ⇒ Object 



24
25
26
 
# File 'lib/complexity_assert/quadratic_complexity_model.rb', line 24

def to_s
  'O(n^2)'
end