タイムアウトを伴うminitestベンチマーク

Question

DPベースのフィボナッチ（fibo）が線形時間を取る間に、素朴な再帰フィボナッチ（fibo_slow）が指数関数的な時間を要することをテストしたいと思います。私はMinitestベンチマークでruby 2.2.2を使用しています。

問題は、再帰フィボナッチが非常に低い値の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は、n = 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を使って2つのフィボナッチアルゴスをテストするのですか？

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