python - 将 memoization 装饰器理解为闭包

Question

我正在尝试学习 Python 装饰器，我想更详细地了解闭包是如何应用的，例如在这个内存上下文中:

def memoize(f):
    memo = {}
    def helper(x):                 
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper   

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

我知道 memoize 返回绑定(bind)到 helper 封闭范围内的 memo 值的函数，即使程序流不是在那个封闭范围内更长。因此，如果 memoize 被重复调用，它将根据 memo 的当前值返回不同的函数序列。我也明白 @memoize 是语法糖，它会导致对 fib(n) 的调用被对 memoize(fib(n)).

我纠结的地方是 fib(n) 中 n 的调用值如何有效地转换为 中的 x助手(x)。大多数关于闭包的教程似乎都没有明确说明这一点，或者他们相当含糊地说一个函数“关闭”另一个函数，这听起来很神奇。我可以看到如何使用语法，但希望更好地了解这里发生的事情以及代码执行时传递的对象和数据。

Answer 1

您误解了 @memoize 装饰器的作用。每次调用 fib 时都不会调用装饰器。对于每个被装饰的函数，装饰器仅调用一次。

原始的 fib 函数被 helper() 函数替换，原始函数对象可用作 f 闭包，连同 memo 闭包:

>>> def fib(n):
...     if n in (0,1):
...         return n
...     return fib(n - 1) + fib(n - 2)
...
>>> fib
<function fib at 0x1023398c0>
>>> memoize(fib)
<function helper at 0x102339758>

这给出了替换 helper 函数 一个 闭包，并且每次调用该 helper() 函数时都是相同的 memo 字典用于为 x 的当前值查找已经生成的结果。

你可以在解释器中看到这一切:

>>> @memoize
... def fib(n):
...     if n in (0,1):
...         return n
...     return fib(n - 1) + fib(n - 2)
...
>>> fib
<function helper at 0x10232ae60>

注意那里的函数名称!那是 helper。它有一个闭包:

>>> fib.__closure__
(<cell at 0x10232d9f0: function object at 0x10232ade8>, <cell at 0x10232da98: dict object at 0x102353050>)

一个函数对象和一个字典，分别是f和memo。使用 .cell_contents 访问单元格内容:

>>> fib.__closure__[0].cell_contents
<function fib at 0x10232ade8>
>>> fib.__closure__[1].cell_contents
{}

这就是原始的装饰函数和空字典。让我们使用这个函数:

>>> fib(0)
0
>>> fib(1)
1
>>> fib.__closure__[1].cell_contents
{0: 0, 1: 1}

这是将 x 设置为 0 和 1 的结果值存储在 memo 字典中。下次我用任一值调用 fib 时，都会使用备忘录。计算并添加新的 x 值:

>>> fib(2)
1
>>> fib.__closure__[1].cell_contents
{0: 0, 1: 1, 2: 1}

您可以通过计算较大的数字需要多长时间来了解它的效果:

>>> start = time.clock(); fib(500); print(format(time.clock() - start, '.10f'))
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L
0.0008390000
>>> start = time.clock(); fib(500); print(format(time.clock() - start, '.10f'))
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L
0.0000220000

>>> start = time.clock(); fib(500); print(format(time.clock() - start, '.10f'))
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L
0.0000190000

第一次调用后，查找memo的速度是所有中间结果都被memo化的40倍:

>>> len(fib.__closure__[1].cell_contents)
501