python之解释这个高阶函数行为

有人可以解释为什么版本 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 

请您参考如下方法:

您的 memoize 函数实际上并没有用 memo_fib 替换 fib，它只是返回一个新函数。

新函数仍然递归调用原始的、未内存的 fib。

所以，基本上，您只是在内存最顶层。

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

所以，简单的解决方法是:

fib = memoize(fib) 

或者只是使用 memoize 作为装饰器，以使其更难出错。

换句话说，您的示例 3 和 4。

或者，更简单地说，使用内置的 lru_cache装饰器。 (请注意其文档中的第二个示例。)

如果您想真正偷偷摸摸:在函数体内定义fib。它将最终引用 fib 作为定义范围的闭包单元，而不是全局的(LOAD_DEREF 而不是反汇编中的 LOAD_GLOBAL)。然后你可以进入那个范围并替换 its fib，这意味着你的递归函数现在被“ secret ”内存(实际的全局 fib没有内存，但它递归调用的函数是)和“安全地”(除了通过 fib 本身，没有其他人有对闭包单元的引用)。