ruby - 为什么哈希递归比 lambda 递归快？

Question

我在 StackOverflow 上找到了两种不同的计算斐波那契数的解决方案。一个使用 lambda，像这样:

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

另一个使用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 版本更快？

Answer 1

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

哈希版本会记住那些之前的计算，只需要进行一次哈希查找，速度非常快。

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