Ruby中不同的memoization技术

Question

如果您是一名红宝石程序员,那么您可能会遇到哈希块记忆模式.在一个简单的例子中,我向您展示了Fibonacci序列的memoized版本:

fib_hash = Hash.new do |h,i|
  h[i] = h[i-1] + h[i-2]
end
# establish the base cases
fib_hash[1] = 1; fib_hash[2] = 1

当然,这不是创建Fibonacci序列的备忘版本的唯一方法.您还可以执行以下操作:

@cache = {}; @cache[1] = 1; @cache[2] = 1
def memo_fib(n)
  @cache[n] ||= (memo_fib(n-1) + memo_fib(n-2))
end

希望你看到哈希块memoization模式如何映射到第二个版本,这在许多其他语言中更为常见.我想知道的是两个版本之间是否有任何区别？我无法摆脱哈希块版本效率更高的感觉,但我无法证明为什么会这样.

Answer 1

MRI 1.8.7的基准产量:

• 哈希块:0.44秒
• 非散列块:0.41秒

在MRI 1.9.0中:

• 哈希块:0.24秒
• 非散列块:0.28秒

基准测试是从1到1000计算Fibonacci数的100次迭代,在每次迭代开始时重置散列或缓存.

这是哈希块的基准:

def reset_fib_hash                                                              
  @fib_hash = Hash.new do |h,i|
    h[i] = h[i-1] + h[i-2]
  end
  # establish the base cases                                                    
  @fib_hash[1] = 1; @fib_hash[2] = 1
end

start_time = Time.now
100.times do
  reset_fib_hash
  (1..1000).each do |i|
    @fib_hash[i]
  end
end
p Time.now - start_time

这是非散列块的基准:

def reset_fib_hash
  @cache = {}; @cache[1] = 1; @cache[2] = 1
end

def memo_fib(n)
  @cache[n] ||= (memo_fib(n-1) + memo_fib(n-2))
end

start_time = Time.now
100.times do
  reset_fib_hash
  (1..1000).each do |i|
    memo_fib(i)
  end
end
p Time.now - start_time