minitest benchmark с таймаутами

Question

Я хочу проверить, что наивная рекурсивная фибоначчи (fibo_slow) занимает экспоненциальное время, в то время как на основе fibonacci на основе DP (fibo) занимает линейное время. Я использую ruby ​​2.2.2 с помощью теста Minitest.

module DSA 
    def self.fibo(n) 
    f = Array.new(n) 
    f[0] = 1 
    f[1] = 1 

    (2..n).each do |i| 
     f[i] = f[i - 1] + f[i - 2] 
    end 

    f[n] 
    end 

    def self.fibo_slow(n) 
    if(n < 2) 
     return 1 
    else 
     return fibo_slow(n - 1) + fibo_slow(n - 2) 
    end 
    end 
end 

Проблема заключается в том, что рекурсивный фибоначчиевый тайм аут при очень низких значениях n. Так что, если я это сделать:

require 'minitest/autorun' 
require 'minitest/benchmark' 

class BenchFibo < Minitest::Benchmark 


    def bench_fibo 
    assert_performance_linear 0.9 do |n| 
     DSA.fibo(n) 
    end 
    end 

    def self.bench_range 
    [1,10,100, 1000, 10000, 100000] 
    end 

    def bench_fibo_slow 

    assert_performance_exponential 0.9 do |n| 
     DSA.fibo_slow(n) 
    end 
    end 
end 

~/Desktop/dsa/rb/dsa : ruby benchmarks/bench_fibo.rb 
Run options: --seed 47332 

# Running: 

bench_fibo 0.000013 0.000010 0.000020 0.000365 0.006358 0.422697 
.bench_fibo_slow  0.000013 0.000017 <hangs at n = 100> 

Чем быстрее fibo проходит утверждение, но fibo_slow не завершат с п = 100 в любое время (гм) в ближайшее время.

Если взять более низкие значения bench_range, подходит не очень точно:

class BenchFibo < Minitest::Benchmark 
    def bench_fibo 
    assert_performance_linear 0.9 do |n| 
     DSA.fibo(n) 
    end 
    end 

    def self.bench_range 
    # [1,10,100, 1000, 10000, 100000] 
    [1,2,4,8,16,32] 
    end 

    def bench_fibo_slow 

    assert_performance_exponential 0.9 do |n| 
     DSA.fibo_slow(n) 
    end 
    end 
end 

~/Desktop/dsa/rb/dsa : ruby benchmarks/bench_fibo.rb 
Run options: --seed 61619 

# Running: 

bench_fibo 0.000017 0.000007 0.000011 0.000011 0.000007 0.000008 
Fbench_fibo_slow  0.000008 0.000007 0.000005 0.000009 0.000138 0.316749 
F 

Finished in 0.360861s, 5.5423 runs/s, 5.5423 assertions/s. 

    1) Failure: 
BenchFibo#bench_fibo [benchmarks/bench_fibo.rb:9]: 
Expected 0.21733687958458803 to be >= 0.9. 

    2) Failure: 
BenchFibo#bench_fibo_slow [benchmarks/bench_fibo.rb:21]: 
Expected 0.5924648214229373 to be >= 0.9. 

2 runs, 2 assertions, 2 failures, 0 errors, 0 skips 

Таким образом, я мог бы добавить тайм-аут для fibo_slow в первом примере кода выше, например, так:

def self.bench_range 
    [1,10,100, 1000, 10000, 100000] 
end 

def bench_fibo_slow 
    assert_performance_exponential 0.9 do |n| 
     begin 
     Timeout::timeout(3) do 
      DSA.fibo_slow(n) 
     end 
     rescue 
     # what could I do here, if anything? 
     end 
    end 
    end 

, но это испортит данные о производительности, и это утверждение никогда не подойдет.

Кроме того, даже когда я бегу с тайм-аут, я получаю необработанную ошибку SystemStackErrorstack level too deep - так, я мог бы, возможно, спасти, что в течение тайм-аута (но нет никакого смысла там, так как сам таймаут развращает подогнанной кривой).

Вопрос в том, как использовать benchmark и assert_performance_xxx для проверки двух фибоначчи-альгос?

Answer 1

Рекурсивный Фибоначчи имеет сложность времени O (2^n) (используя формулу O (ветви^глубина) - why 2^n?), поэтому это функция мощности вместо экспоненциальной. Он работает со следующей конфигурацией для меня:

def self.bench_range 
    [25, 30, 35] # Smaller values seem problematic 
end 

def bench_fibo_slow 
    assert_performance_power 0.9 do |n| 
    DSA.fibo_slow(n) 
    end 
end