2

我在 StackOverflow 上找到了两种不同的解决方案来计算斐波那契数。一个使用 a lambda，如下所示：

f = ->(x){ x < 2 ? x : f[x-1] + f[x-2] }
f[6] # => 8

另一个使用 a Hash：

f = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }
f[6] # => 8

版本比Hash版本快lambda。

Benchmark.bm do |x|
  x.report { f[35] }
  x.report { fibonacci[35] }
end

user       system     total      real
7.332000   0.000000   7.332000  (7.349421)
0.000000   0.000000   0.000000  (0.000000)

该lambda版本甚至无法f[100]在合理的时间内Hash进行计算，而该版本可以fibonacci[1000]在不到一微秒的时间内进行计算。为什么Hash版本更快？

4

3 回答 3

5

部分原因是 lambda 版本必须f[x-1] + f[x-2]为每个新数字重新计算，并且它必须随着x变大而递归地执行此操作。

哈希版本会记住那些之前的计算，并且只需要进行哈希查找，这是非常快的。

可以修改 lambda 版本以使用 memoization 或通过用作缓存的外部哈希来缩短重新计算。它需要更多的代码和更多的内存，但这与哈希版本相当。

于 2013-06-17T17:53:05.020 回答
2

Hash 版本将计算的数据保存在内存中，而 lambda 版本不保存。

如果您运行 hash_fibonnacci[10] 并打印对象：“p hash_fibonnacci”，您将看到计算出的所有中间结果。

每个 lambda 调用都会递归地重做所有计算，直到数字 2。当您调用 lambda_fibonnacci[10] 时，它计算了大约 170 次，而 Hash 实现仅 10 次。

于 2013-06-17T17:52:26.230 回答
0

对斐波那契进行递归只是一种错误的方法，在到达边缘条件之前，您正在创建一个巨大的调用树。可以通过使用尾递归轻松避免（虽然在 Ruby 中没有优化）：

f = 
  lambda do |x| 
    f0 = 
      lambda do |a, b, y| 
        y > 0 ? f0[b, a + b, y - 1] : a
      end
    f0[0, 1, x]
  end
p (0..100).map(&f)
于 2013-06-17T20:14:43.690 回答