为什么这个memoizer适用于递归函数？

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是不在缓存中,它会调用obj上100.但这obj是原始的fib功能,所以不应该花费同样长的时间(在第一次评估时),就好像我们根本没有记忆一样？

Answer 1

obj在装饰器中确实是包装的,未修改的,非记忆功能.但是,当所述函数尝试递归时,它会查找全局名称fib,获取memoized包装函数,因此也会导致第99,第98,...斐波那契数字沿途被记忆.

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