英文:
Why does timeit results in almost constant time for all memoization runs?
问题
我们计算斐波那契数列：
def fibo_memo(i, memo={}):
if i <= 0:
return 0
elif i == 1:
return 1
elif i in memo:
return memo[i]
else:
memo[i] = fibo_memo(i-2, memo) + fibo_memo(i-1, memo)
return memo[i]
def fibo_dp(i):
if i <= 0:
return 0
elif i == 1:
return 1
dp = [0] * (i + 1)
dp[1] = 1
for j in range(2, i + 1):
dp[j] = dp[j-1] + dp[j-2]
return dp[i]
assert(fibo_memo(100) == fibo_dp(100))
现在计时：
i = 10
%timeit fibo_memo(i) # 73 ns
%timeit fibo_dp(i) # 309 ns
i = 100
%timeit fibo_memo(i) # 73 ns
%timeit fibo_dp(i) # 2.54 微秒
i = 1000
%timeit fibo_memo(i) # 73 ns
%timeit fibo_dp(i) # 33 微秒
为什么记忆化方法的执行时间几乎是常数时间，而动态规划不是？
英文:
We compute the Fibonacci number:
def fibo_memo(i, memo={}):
if i <= 0:
return 0
elif i == 1:
return 1
elif i in memo:
return memo[i]
else:
memo[i] = fibo_memo(i-2, memo) + fibo_memo(i-1, memo)
return memo[i]
def fibo_dp(i):
if i <= 0:
return 0
elif i == 1:
return 1
dp = [0] * (i + 1)
dp[1] = 1
for j in range(2, i + 1):
dp[j] = dp[j-1] + dp[j-2]
return dp[i]
assert(fibo_memo(100) == fibo_dp(100))
Now time it:
i = 10
%timeit fibo_memo(i) # 73 ns
%timeit fibo_dp(i) # 309 ns
i = 100
%timeit fibo_memo(i) # 73 ns
%timeit fibo_dp(i) # 2.54 micro seconds
i = 1000
%timeit fibo_memo(i) # 73 ns
%timeit fibo_dp(i) # 33 micro seconds
Why does memoization result in almost constant time, unlike dynamic programming?
答案1
得分: 2
"mutable default argument of fibo_memo"（fibo_memo的可变默认参数）在%timeit迭代之间保持不变，其中包含记忆化的值，因此除了第一次迭代外，所有迭代都几乎瞬间完成。 （实际上，对于i = 10和i = 100，第一次迭代可能也几乎瞬间完成，因为assert检查将记忆化字典填充到100。）
为了进行一对一的比较，每次都应该使用空的记忆化字典来调用fibo_memo：
i = 10
%timeit fibo_memo(i, {})
%timeit fibo_dp(i)
i = 100
%timeit fibo_memo(i, {})
%timeit fibo_dp(i)
i = 1000
%timeit fibo_memo(i, {})
%timeit fibo_dp(i)
在我在Google Colab上的快速运行中，这显示出了两种解决方案的非常相似的缩放行为（大致符合预期的O(N)，记忆化解决方案对于每个i值大约需要DP的3倍时间）。
英文:
The mutable default argument of fibo_memo, which holds the memoized values, persists between iterations of %timeit. So all but the first iteration complete near-instantly. (And in fact, for i = 10 and i = 100, the first iteration is probably near-instant too, since the assert check populated the memoization dict up to 100.)
For a like-for-like comparison, fibo_memo should be called with an empty memoization dict each time:
i = 10
%timeit fibo_memo(i, {})
%timeit fibo_dp(i)
i = 100
%timeit fibo_memo(i, {})
%timeit fibo_dp(i)
i = 1000
%timeit fibo_memo(i, {})
%timeit fibo_dp(i)
In my quick run on Google Colab, this shows very similar scaling behaviour for both solutions (roughly the expected O(N), with the memoization solution taking about 3 times as long as the DP for each value of i).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论