타임 아웃이있는 가장 작은 벤치 마크

Question

DP 기반 피보나치 (fibo)가 선형 시간이 걸리는 동안 순진한 재귀 피보나치 (fibo_slow)는 기하 급수적 인 시간이 걸리는지 테스트하고 싶습니다. Minitest 벤치 마크에서 ruby ​​2.2.2를 사용하고 있습니다.

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는 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 

하지만 성능 데이터가 엉망이되어 어설 션이 적합하지 않습니다. 그래서, 나는 어쩌면 제한 시간 내에 그 구출 수있다 (그러나 타임 아웃 자체가 장착되어 곡선을 손상 때문에 아무 소용이있다 없음) - 내가 타임 아웃으로 실행할 때

는 또한, 심지어 내가 처리되지 않은 오류 SystemStackError stack level too deep를 얻을.

내 질문은 benchmark과 assert_performance_xxx을 사용하여 두 개의 fibonacci algos를 테스트하는 것입니다.

Answer 1

재귀 피보나치는 O (분기^깊이) 수식 (why 2^n?)을 사용하여 O (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