追忆技术
追忆技术
提问于 2014-05-03 14:05:41
在尝试一些回忆录技巧时，我无意中发现了这个基准结果，这与我的期望是背道而驰的。似乎我在犯一些愚蠢的错误，有人看到我做错了什么吗？(基准测试给出了类似的回忆录代码和非回忆录代码的结果)？
require 'benchmark'
# -----------------------------------------
class FactorialClass
@@sequence = [1]
def self.of( n )
@@sequence[n] || n * of( n - 1 )
end
end
# -----------------------------------------
def factorial_with_memoization
sequence = [1]
lambda = Proc.new do |n|
sequence[n] || n * lambda.call( n - 1 )
end
end
f = factorial_with_memoization()
# -----------------------------------------
def factorial n
n == 0 ? 1 : n * factorial( n - 1 )
end
# -----------------------------------------
count = 1_000
n = 1000
without_memoization = Benchmark.measure do
count.times do
factorial(n)
end
end
with_memoization_lambda = Benchmark.measure do
count.times do
f.call(n)
end
end
with_memoization_class = Benchmark.measure do
count.times do
FactorialClass.of(n)
end
end
puts "Without memoization : #{ without_memoization }"
puts "With memoization using lambda : #{ with_memoization_lambda }"
puts "With memoization using class : #{ with_memoization_class }"**结果如下：**
Without memoization : 1.210000 0.100000 1.310000 ( 1.309675)
With memoization using lambda : 1.750000 0.100000 1.850000 ( 1.858737)
With memoization using class : 1.270000 0.090000 1.360000 ( 1.358375)回答 1
Stack Overflow用户
回答已采纳
发布于 2014-05-03 14:49:04
您从不向缓存分配任何已记忆的值。就像@xlembouras说的，你什么都没记住。
class FactorialClass
@@sequence = [1]
def self.of( n )
# @@sequence[n] get evaluated to nil unless n is 0, always!
@@sequence[n] || n * of( n - 1 )
end
end在完成计算之后，您需要手动将记忆的值分配给缓存。
class FactorialClass
@@sequence = [1]
def self.of( n )
@@sequence[n] = (@@sequence[n] || n * of( n - 1 ))
end
end然而，记忆真的适用于你的阶乘计算吗？不是的。
f(n) = n * f(n-1) = n * ((n-1) * f(n-2)) = ... = n * ((n-1) * (... * (3 * f(2))))所有递归步骤都计算一个新值(从2到n)的阶乘，这是以前没有计算过的。记忆不会在任何步骤中被击中。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23445461
复制相关文章
相似问题
腾讯云开发者
