python - 为什么即使没有重复计算，memoization 也可以加速 Python 中的阶乘？

Question

这是我的代码。

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

为什么慢？是不是因为函数内部产生的值暂时存在栈中？外面的变量是全局的，但是是什么让它这么快呢？有人会好心帮我清理一下吗？我将不胜感激。

Answer 1

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

因此，您内存的阶乘函数只会在它实际必须进行计算的第一次执行时变慢。剩下的 999999 次它会简单地在字典中查找答案并避免进行计算。

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

Check out the documentation for timeit.