解释这个高阶函数行为

问题描述：

有人可以解释为什么版本1和2以相同的速度执行吗？我预计版本2,3和4需要大约相同的时间。解释这个高阶函数行为

def fib(n): 
    return n if n in [0, 1] else fib(n-2)+fib(n-1) 

def memoize(fn): 
    stored_results = {} 

    def memoized(*args): 
     try: 
      return stored_results[args] 
     except KeyError: 
      #nothing cached 
      result = stored_results[args] = fn(*args) 
      return result 

    return memoized 

#version 1 (unmemoized) 
print timeit.timeit('fib(35)', 'from __main__ import fib', number=1) 
print fib, '\n' 

#version 2 
memo_fib = memoize(fib) 
print timeit.timeit('memo_fib(35)', 'from __main__ import memo_fib', number=1) 
print memo_fib, '\n' 

#version 3 (wrapped) 
fib = memoize(fib) 
print timeit.timeit('fib(35)', 'from __main__ import fib', number=1) 
print fib, '\n' 

#version 4 (w/ decoration line) 
@memoize 
def fib(n): 
    return n if n in [0, 1] else fib(n-2)+fib(n-1) 

print timeit.timeit('fib(35)', 'from __main__ import fib', number=1)

结果：

version 1: 4.95815300941 
<function fib at 0x102c2b320> 

version 2: 4.94982290268 
<function memoized at 0x102c2b410> 

version 3: 0.000107049942017 
<function memoized at 0x102c2b488> 

version 4: 0.000118970870972

使用'timeit'模块为您的代码计时。 – 2013-04-30 23:50:36

答

你memoize功能实际上并没有取代fib与memo_fib，它只是返回一个新功能。

该新功能仍递归调用原始未记忆的fib。

所以，基本上，你只是记忆的最高水平。

在fib，以fib递归调用时只使用模块的全局名称。（函数与其他任何类型的值基本没有区别，函数名称与其他类型的名称没有区别，所以如果您在模块全局级别定义函数，那就是它的作用，例如，如果您反编译字节码与dis.dis(fib)，你会看到名字fib一个LOAD_GLOBAL）

所以，简单的解决办法是：

fib = memoize(fib)

或者只是使用memoize作为装饰，使这个更难得到错误的。

换句话说，你的例子3和4

或者，甚至更简单，使用内置lru_cache装饰。一个函数体内定义fib：如果你想成为真正偷偷摸摸（注意它的文档中的第二个例子。）

。它将最终引用fib作为定义范围内的封闭单元，而不是全局（LOAD_DEREF而不是LOAD_GLOBAL在反汇编中）。然后，您可以进入该范围并替换其其fib，这意味着您的递归函数现在被“秘密地”记忆（实际的全局fib未被记忆，但递归调用的函数是）和“安全”（没有人除了通过fib本身以外，其他人对闭合单元有参考）。

答

在版本2中，您使用不同的名称存储了memoized版本，因此您可以调用fib的次数与第一次版本中的次数相同。您的调用堆栈看起来是这样的：

memo_fib(35) 
    fib(35) 
     fib(34) 
      fib(33) 
     fib(33)

等

所以你实际上并没有收到在此情况下，记忆化任何好处。

解释这个高阶函数行为

相关推荐