1

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

2 回答 2

5

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

这个新函数仍然递归地调用原始的 un-memoized 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自身）。

于 2013-04-30T23:54:24.407 回答
1

在版本 2 中，您使用不同的名称存储了 memoized 版本，因此您最终调用 fib 的次数与在第一个版本中一样多。您的调用堆栈如下所示：

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

等等

所以在这种情况下，你实际上并没有从记忆中获得任何好处。

于 2013-04-30T23:56:23.097 回答