为什么这个记忆化函数能够用于递归函数？

Question

我不明白为什么以下代码使得fib函数的运行时间是线性，而不是指数级。

def memoize(obj):
    """Memoization decorator from PythonDecoratorLibrary. Ignores
    **kwargs"""

    cache = obj.cache = {}

    @functools.wraps(obj)
    def memoizer(*args, **kwargs):
        if args not in cache:
            cache[args] = obj(*args, **kwargs)
        return cache[args]
    return memoizer

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

例如，fib(100)并没有像我预期的那样完全崩溃。

我的理解是@memoize设置了fib=memoize(fib)。因此，当您调用fib(100)时，会发现100不在缓存中，它将在100上调用obj。但是obj是原始的fib函数，所以它是否需要像没有记忆化一样花费同样长的时间（第一次评估）？

- JohnJamesSmith0

Answer 1

装饰器中的obj实际上是被包装的、未修改的、非记忆化函数。然而，当该函数尝试递归时，它查找全局名称fib，获取记忆化的包装函数，并因此沿途也导致了第99个、第98个...斐波那契数列被记忆化。

- user395760

Answer 2

名称是按词法解析的。仅仅因为你从名为fib的函数中调用了一个名为fib的函数，这并不意味着它一定是同一个fib。

下面是一个（高度不准确的）演示：

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

由于装饰器影响全局变量globals，因此在递归调用发生时，您会得到经过装饰的fib。

- shx2

Answer 3

“但是obj是原始的fib函数，所以在第一次评估时，它不应该像没有记忆化一样需要同样长的时间吗？”

memoizer中的obj确实是原始的fib函数。技巧在于，当fib递归调用自身时，它会调用memoize(fib)。

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

在这里，wrapped是由functools生成的函数，调用memoize.memoizer。有点像。

递归调用最终可能会变成简单的查找obj.cache（理论上是O(1)），这就是显著提高性能的原因。

- dragonx