解释这个高阶函数行为

Question

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

Answer 1

您的memoize功能实际上并没有替换fib用memo_fib,它只是返回一个新功能.

这个新函数仍然以递归方式调用原始的,未记忆的fib.

所以,基本上,你只记得最高级别.

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

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

fib = memoize(fib)

或者只是memoize作为装饰者使用,以使这更难出错.

换句话说,你的例子3和4.

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

如果你想成为真正的偷偷摸摸:定义fib一个函数体内.它将最终fib作为定义范围的闭包单元引用,而不是全局(LOAD_DEREF而不是LOAD_GLOBAL反汇编).然后你可以进入那个范围并替换它 fib,这意味着你的递归函数现在被"秘密地"记忆(实际的全局fib没有被记忆,但它递归调用的函数是)和"安全"(没有其他人有参考)封闭细胞除了通过fib自身).