1

这是我的代码。

import timeit

fac_mem = {}

def fac(k):
  if k < 2: return 1
  if k not in fac_mem:
    fac_mem[k] = k*fac(k-1)
return fac_mem[k]

def fact(k):
  if k < 2: return 1
  return k*fact(k-1)

if __name__ == "__main__": 
  print timeit.timeit("fac(7)","from __main__ import fac")
  print timeit.timeit("fact(7)","from __main__ import fact")
  print timeit.timeit("fac(70)","from __main__ import fac")
  print timeit.timeit("fact(70)","from __main__ import fact")

这是输出

0.236774399224
0.897065011572
0.217623144304
14.1952226578

好吧，在程序运行之前，dict是空的，为什么memoization仍然加快了阶乘？我的意思是，这两个版本的调用次数是相同的。然后我稍微更改了代码，将 dict 移到函数中。

def fac(k):
  fac_mem = {}
  if k < 2: return 1
  if k not in fac_mem:
    fac_mem[k] = k*fac(k-1)
  return fac_mem[k]

输出改变了

1.92900857225
0.910026658388
25.5475004875
14.2164999769

为什么慢？那是因为函数内部生成的值暂时存储在堆栈中吗？外部变量是全局变量，但是是什么让它变得如此之快？有人可以帮我清理一下吗？我将不胜感激。

4

2 回答 2

4

当您在timeit.timeit没有为关键字指定参数的情况下运行时number，它会执行您传递给它的代码 1000000 次。如果您在 Python 的全局范围内保存一个全局字典fac_mem，它将在该字典中保存第一次执行的结果。

因此，您的记忆阶乘函数只会在第一次执行时很慢，因为它实际上必须进行计算。剩下的 999999 次它只会在字典中查找答案并避免进行计算。

如果将字典保留在函数内，则每次 Python 离开函数内的范围后，它都会被销毁（因为当函数返回时，对字典的所有引用都将被销毁）。因此，字典将无法保存它的答案，并且对于未来的执行仍然很慢。

查看timeit.

于 2013-09-22T02:47:13.773 回答
3
  1. 你写的备忘录永久挂在答案上。这意味着多次询问相同的答案非常快。只有第一次调用需要计算任何东西。
  2. timeit 对函数进行基准测试的方式是运行它数百次并取所有调用的平均值。这有助于它更准确

这意味着 1 个正常速度呼叫和 99 个超快速呼叫一起平均。这使得 memoized 函数看起来更快。

如果你想测量实际速度，你需要在每次测试调用后清除你的记忆字典。

于 2013-09-22T02:47:16.983 回答