Module: Benchmark::Trend

Defined in:
lib/benchmark/trend.rb,
lib/benchmark/trend/clock.rb,
lib/benchmark/trend/version.rb

Defined Under Namespace

Modules: Clock

Constant Summary collapse

FIT_TYPES =

the trends to consider

[:exponential, :power, :linear, :logarithmic]
VERSION = 
"0.4.0"

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.fit(xs, ys, tran_x: ->(x) { x }, tran_y: ->(y) { y }) ⇒ Array[Numeric, Numeric, Numeric]

Fit the performance measurements to construct a model with slope and intercept parameters that minimize the error. returns slope, intercept and model’s goodness-of-fit] Array[Numeric, Numeric, Numeric]

returns slope, intercept and model's goodness-of-fit

Parameters:

  • xs (Array[Numeric]) —

    the data points along X axis

  • ys (Array[Numeric]) —

    the data points along Y axis

Returns:

  • (Array[Numeric, Numeric, Numeric]) —

    Array[Numeric, Numeric, Numeric]



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/benchmark/trend.rb', line 180

def fit(xs, ys, tran_x: ->(x) { x }, tran_y: ->(y) { y })
  eps    = (10 ** -10)
  n      = 0
  sum_x  = 0.0
  sum_x2 = 0.0
  sum_y  = 0.0
  sum_y2 = 0.0
  sum_xy = 0.0

  xs.zip(ys).each do |x, y|
    n        += 1
    sum_x    += tran_x.(x)
    sum_y    += tran_y.(y)
    sum_x2   += tran_x.(x) ** 2
    sum_y2   += tran_y.(y) ** 2
    sum_xy   += tran_x.(x) * tran_y.(y)
  end

  txy = n * sum_xy - sum_x * sum_y
  tx  = n * sum_x2 - sum_x ** 2
  ty  = n * sum_y2 - sum_y ** 2

  is_linear = tran_x.(Math::E) * tran_y.(Math::E) == Math::E ** 2

  if tx.abs < eps # no variation in xs
    raise ArgumentError, "No variation in data #{xs}"
  elsif ty.abs < eps && is_linear # no variation in ys - constant fit
    slope = 0
    intercept = sum_y / n
    residual_sq = 1 # doesn't exist
  else
    slope       = txy / tx
    intercept   = (sum_y - slope * sum_x) / n
    residual_sq = (txy ** 2) / (tx * ty)
  end

  [slope, intercept, residual_sq]
end

.fit_at(type, slope: nil, intercept: nil, n: nil) ⇒ Object

Take a fit and estimate behaviour at input size n

Examples:

fit_at(:power, slope: 1.5, intercept: 2, n: 10)

Returns:

  • fit model value for input n

Raises:

  • (ArgumentError) 


229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'lib/benchmark/trend.rb', line 229

def fit_at(type, slope: nil, intercept: nil, n: nil)
  raise ArgumentError, "Incorrect input size: #{n}" unless n > 0

  case type
  when :logarithmic, :log
    intercept + slope * Math.log(n)
  when :linear
    intercept + slope * n
  when :power
    intercept * (n ** slope)
  when :exponential, :exp
    intercept * (slope ** n)
  else
    raise ArgumentError, "Unknown fit type: #{type}"
  end
end

.fit_exp ⇒ Numeric

Find a line of best fit that approximates exponential function

Model form: y = ab^x

Returns:

  • (Numeric, Numeric, Numeric) —

    returns a, b, and rr values



164
165
166
167
168
 
# File 'lib/benchmark/trend.rb', line 164

def fit_exponential(xs, ys)
  a, b, rr = fit(xs, ys, tran_y: ->(y) { Math.log(y) })

  [Math.exp(a), Math.exp(b), rr]
end

.fit_exponential(xs, ys) ⇒ Numeric

Find a line of best fit that approximates exponential function

Model form: y = ab^x

Returns:

  • (Numeric, Numeric, Numeric) —

    returns a, b, and rr values



157
158
159
160
161
 
# File 'lib/benchmark/trend.rb', line 157

def fit_exponential(xs, ys)
  a, b, rr = fit(xs, ys, tran_y: ->(y) { Math.log(y) })

  [Math.exp(a), Math.exp(b), rr]
end

.fit_linear(xs, ys) ⇒ Numeric

Finds a line of best fit that approximates linear function

Function form: y = ax + b

Parameters:

  • xs (Array[Numeric]) —

    the data points along X axis

  • ys (Array[Numeric]) —

    the data points along Y axis

Returns:

  • (Numeric, Numeric, Numeric) —

    return a slope, b intercept and rr correlation coefficient



106
107
108
 
# File 'lib/benchmark/trend.rb', line 106

def fit_linear(xs, ys)
  fit(xs, ys)
end

.fit_log ⇒ Numeric

Find a line of best fit that approximates logarithmic function

Model form: y = a*lnx + b

Parameters:

  • xs (Array[Numeric]) —

    the data points along X axis

  • ys (Array[Numeric]) —

    the data points along Y axis

Returns:

  • (Numeric, Numeric, Numeric) —

    returns a, b, and rr values



130
131
132
 
# File 'lib/benchmark/trend.rb', line 130

def fit_logarithmic(xs, ys)
  fit(xs, ys, tran_x: ->(x) { Math.log(x) })
end

.fit_logarithmic(xs, ys) ⇒ Numeric

Find a line of best fit that approximates logarithmic function

Model form: y = a*lnx + b

Parameters:

  • xs (Array[Numeric]) —

    the data points along X axis

  • ys (Array[Numeric]) —

    the data points along Y axis

Returns:

  • (Numeric, Numeric, Numeric) —

    returns a, b, and rr values



125
126
127
 
# File 'lib/benchmark/trend.rb', line 125

def fit_logarithmic(xs, ys)
  fit(xs, ys, tran_x: ->(x) { Math.log(x) })
end

.fit_power(xs, ys) ⇒ Numeric

Finds a line of best fit that approxmimates power function

Function form: y = bx^a

Returns:

  • (Numeric, Numeric, Numeric) —

    returns a, b, and rr values



141
142
143
144
145
146
 
# File 'lib/benchmark/trend.rb', line 141

def fit_power(xs, ys)
  a, b, rr = fit(xs, ys, tran_x: ->(x) { Math.log(x) },
                         tran_y: ->(y) { Math.log(y) })

  [a, Math.exp(b), rr]
end

.format_fit(type) ⇒ String

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

A mathematical notation template for a trend type

Parameters:

  • type (String) —

    the fit model type

Returns:

  • (String) —

    the formatted mathematical function template



256
257
258
259
260
261
262
263
264
265
266
267
268
269
 
# File 'lib/benchmark/trend.rb', line 256

def format_fit(type)
  case type
  when :logarithmic, :log
    "%.2f + %.2f*ln(x)"
  when :linear, :constant
    "%.2f + %.2f*x"
  when :power
    "%.2f * x^%.2f"
  when :exponential, :exp
    "%.2f * %.2f^x"
  else
    raise ArgumentError, "Unknown type: '#{type}'"
  end
end

.infer_trend(data, repeat: 1) {|work| ... } ⇒ Array[Symbol, Hash]

Infer trend from the execution times

Fits the executiom times for each range to several fit models.

Parameters:

  • repeat (Integer) (defaults to: 1) —

    nubmer of times work is called to compute execution time

Yield Parameters:

  • work —

    the block of which the complexity is measured

Returns:

  • (Array[Symbol, Hash]) —

    the best fitting and all the trends



289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
 
# File 'lib/benchmark/trend.rb', line 289

def infer_trend(data, repeat: 1, &work)
  ns, times = *measure_execution_time(data, repeat: repeat, &work)
  best_fit = :none
  best_residual = 0
  fitted = {}
  n = ns.size.to_f
  aic = -1.0/0
  best_aic = -1.0/0

  FIT_TYPES.each do |fit|
    a, b, rr = *send(:"fit_#{fit}", ns, times)
    # goodness of model
    aic = n * (Math.log(Math::PI) + 1) + n * Math.log(rr / n)
    if a == 0 && fit == :linear
      fit = :constant
    end
    fitted[fit] = { trend: format_fit(fit) % [a, b],
                    slope: a, intercept: b, residual: rr }
    if rr >= best_residual && aic >= best_aic
      best_residual = rr
      best_fit = fit
      best_aic = aic
    end
  end

  [best_fit, fitted]
end

.measure_execution_time(data = nil, repeat: 1, &work) ⇒ Array[Array, Array]

Gather times for each input against an algorithm

Parameters:

  • data (Array[Numeric]) (defaults to: nil) —

    the data to run measurements for

  • repeat (Integer) (defaults to: 1) —

    nubmer of times work is called to compute execution time

Returns:

  • (Array[Array, Array]) 


74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/benchmark/trend.rb', line 74

def measure_execution_time(data = nil, repeat: 1, &work)
  inputs = data || range(1, 10_000)
  times  = []

  inputs.each_with_index do |input, i|
    GC.start
    measurements = []

    repeat.times do
      measurements << Clock.measure { work.(input, i) }
    end

    times << measurements.reduce(&:+).to_f / measurements.size
  end
  [inputs, times]
end

.private_module_function(method) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Change module function visiblity to private



11
12
13
14
 
# File 'lib/benchmark/trend.rb', line 11

def self.private_module_function(method)
  module_function(method)
  private_class_method(method)
end

.range(start, limit, ratio: 8) ⇒ Object

Generate a range of inputs spaced by powers.

The default range is generated in the multiples of 8.

Examples:

Benchmark::Trend.range(8, 8 << 10)
# => [8, 64, 512, 4096, 8192]

Parameters:

  • start (Integer)
  • limit (Integer)
  • ratio (Integer) (defaults to: 8) 


29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/benchmark/trend.rb', line 29

def range(start, limit, ratio: 8)
  check_greater(start, 0)
  check_greater(limit, start)
  check_greater(ratio, 2)

  items = []
  count = start
  items << count
  (limit / ratio).times do
    count *= ratio
    break if count >= limit
    items << count
  end
  items << limit if start != limit
  items
end

Instance Method Details

#check_greater(expected, min) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Check if expected value is greater than minimum

Parameters:

  • expected (Numeric)
  • min (Numeric)

Raises:

  • (ArgumentError) 


55
56
57
58
59
60
 
# File 'lib/benchmark/trend.rb', line 55

def check_greater(expected, min)
  unless expected >= min
    raise ArgumentError,
          "Range value: #{expected} needs to be greater than #{min}"
  end
end