为什么此备注程序在递归函数上起作用? [英] Why does this memoizer work on recursive functions?

问题描述

我不知道为什么下面的代码使fib在线性而不是指数时间内运行.

I can't figure out why the following code is makes fib run in linear rather than exponential time.

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)并没有像我预期的那样完全爆炸.

For example, fib(100) doesn't completely blow up like I expected it to.

我的理解是@memoize设置了fib = memoize(fib).因此，当您调用fib(100)时，看到100不在缓存中，它将在100上调用obj.但是obj是原始的fib函数，所以(在第一次评估中)它是否花的时间就好像我们根本没有记忆一样?

My understanding is that @memoize sets fib = memoize(fib). So when you call fib(100), seeing that 100 is not in the cache, it will call obj on 100. But obj is the original fib function, so shouldn't it take just as long (on the first evaluation) as if we didn't have memoization at all?

推荐答案

名称按词法解析 .仅仅是因为您从名为fib的函数中调用了名为fib的函数，但这并不意味着它必须与fib相同.

Names are resolved lexically. Just because you call a function named fib from within a function named fib, that doesn't mean it would necessarilly be the same fib.

关于发生的事情的一个(非常不准确的)演示是这样的:

A (highly inaccurate) demonstration of what's going on is this:

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

由于修饰器会影响globals，因此在进行递归调用时会得到修饰的fib.

Since the decorater affects globals, you get the decorated fib at the time the recursive call occurs.

这篇关于为什么此备注程序在递归函数上起作用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！