循环如何在装饰器中工作（记忆）

Question

记忆是一个强大的工具。我试图了解基本的机制，但是它似乎并没有按照我的想法工作。谁能在下面的代码中详细解释它的工作原理？

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

    return helper

@memoize
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

真正让我困惑的是，在此示例中，装饰器memoize投入使用。根据tutorial，似乎要装饰的整个功能在装饰器中运行。这里的功能是fib(n)。如果是这样，如何在装饰器fib(n)中处理memoize(f)中的循环？

让我们以fib(4)为例来说明过程的神秘性：

In [1]: fib(4)
{1: 1}
{1: 1, 0: 0}
{1: 1, 0: 0, 2: 1}
{1: 1, 0: 0, 2: 1}
{1: 1, 0: 0, 2: 1, 3: 2}
{1: 1, 0: 0, 2: 1, 3: 2}
{1: 1, 0: 0, 2: 1, 3: 2, 4: 3}

为什么在memoize(f)中打印的第一个值是{1: 1}？我希望memoize(f)在一开始就存储备忘= {4：f（4）}，即使当时尚不知道f（4）的值。我知道我错了。谁能解释我们如何获得这些输出以及fib(n)中的循环如何在memoize(f)中工作？

非常感谢。

Answer 1

在函数调用返回之前，不会填充memo缓存：

memo[x] = f(x)

由于循环是递归的，因此在第一个f完成返回并填充缓存之前，还有很多对f(4)的调用。这些实际返回的调用中的第一个是f(1)，然后是f(0)等（如您的打印语句所示）。

如果要在print的开头添加另一个helper（之前]，请调用f），那么您会发现递归调用是一个三明治，其中f(4)首先开始，但最后最后。

这是修改打印语句以显示递归深度的方法：

def memoize(f):
    memo = {}
    depth = [0]
    def helper(x):
        print(f"{'  '*depth[0]}Calling f({x})...")
        depth[0] += 1
        if x not in memo:            
            memo[x] = f(x)
        print(f"{'  '*depth[0]}Cached: {memo}")
        depth[0] -= 1
        print(f"{'  '*depth[0]}Finished f({x})!")
        return memo[x]

    return helper

@memoize
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)
打印：

Calling f(4)...
  Calling f(3)...
    Calling f(2)...
      Calling f(1)...
        Cached: {1: 1}
      Finished f(1)!
      Calling f(0)...
        Cached: {1: 1, 0: 0}
      Finished f(0)!
      Cached: {1: 1, 0: 0, 2: 1}
    Finished f(2)!
    Calling f(1)...
      Cached: {1: 1, 0: 0, 2: 1}
    Finished f(1)!
    Cached: {1: 1, 0: 0, 2: 1, 3: 2}
  Finished f(3)!
  Calling f(2)...
    Cached: {1: 1, 0: 0, 2: 1, 3: 2}
  Finished f(2)!
  Cached: {1: 1, 0: 0, 2: 1, 3: 2, 4: 3}
Finished f(4)!

Answer 2

首先，了解装饰器（不带参数）的最简单方法是查看以下等效项