带超时的迷你测试基准

Question

我想测试朴素递归斐波那契 (fibo_slow) 需要指数时间，而基于 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 不会很快完成 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 来测试两个斐波那契算法？

Answer 1

递归斐波那契具有 O(2^n) 时间复杂度（使用 O(branches ^ depth) 公式 - 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

带超时的迷你测试基准

minitest benchmark with timeouts

ruby

benchmarking

minitest