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

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 函数实际上并没有用 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 本身，没有其他人有对闭包单元的引用)。