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

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)。如果是这样，装饰器 memoize(f) 中的 fib(n) 中的循环是如何处理的？

我们以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) 在一开始就存储 memo = {4 : f(4)}，即使当时还不知道 f(4) 的值。我知道我错了。谁能解释一下我们如何获得这些输出以及 fib(n) 中的循环如何在 memoize(f) 中工作？

非常感谢。

Answer 1

在函数调用 returns:

之前，memo 缓存不会被填充

memo[x] = f(x)

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

如果您要在 helper 的开头添加另一个 print（在您调用 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

首先，理解装饰器（不带参数）最简单的方法是看下面的等价关系

@memoize
def f():
    ...

# is the same as


def f():
   ...
f = memoize(f)

因此代码

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

等同于

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

def fib(x):
    if x not in memo:            
        memo[x] = not_decorated_fib(x)
    print(memo)
    return memo[x]

这意味着您将拥有以下调用堆栈：

堆栈级别 0：fib(4) 调用 not_decorated_fib(4) 因为 memo 是空
堆栈级别 1：not_decorated_fib(4) 调用 fib(3)（+ fib(2) 只会在 fib(3) 已解决后调用）
堆栈级别 2：fib(3) 调用 not_decorated_fib(3)，因为 memo 是仍然是空的
堆栈级别 3：not_decorated_fib(3) 调用 fib(2)
堆栈级别 4：fib(2) 调用 not_decorated_fib(2) 因为 memo 是还是空的
堆栈级别 5：not_decorated_fib(2) 调用 fib(1)
堆栈级别 6：fib(1) 调用 not_decorated_fib(1) 因为 memo 是还是空的
堆栈级别 7：not_decorated_fib(1) returns 1（结束条件）
堆栈级别 6: fib(1): memo[1] 自 not_decorated_fib(1) 以来设置，我们得到第一个打印 {1:1} 和 fib(1) returns 1
堆栈级别 5：not_decorated_fib(2) 调用 fib(0)（fib(1) + fib(0) 第二部分的评估）
堆栈级别 6：fib(0) 调用 not_decorated_fib(0)
堆栈级别 7：not_decorated_fib(0) returns 0（结束条件）
堆栈级别 6：fib(0)：memo[0] 自 not_decorated_fib(0) 以来设置，我们得到第二个打印 {1:1, 0:0} 和 fib(0) returns 0

并且以类似的方式执行函数的其余部分

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

How does loop work in decorator (memoization)

python

decorator

memoization