Python 函数的备忘录法

Question

这里有一段小代码，可以把每个函数转换成带有记忆功能的版本。

def memoize(f): # Memoize a given function f
    def memf(*x):
        if x not in memf.cache:
            memf.cache[x] = f(*x)
        return memf.cache[x]

    memf.cache = {}
    return memf

比如说，我们有一个函数 fib，它可以返回第 n 个斐波那契数：

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

现在，上面的函数可以通过以下方式进行记忆化处理：

fib = memoize(fib)

到目前为止一切都很好，但我不明白的是，如果我们这样做，而不是：

fib = memoize(fib)

我们反而这样做：

fib2 = memoize(fib)

那么函数 fib2 就不是 fib 的记忆化版本。当我们运行 fib2 时，它就像普通的 fib 一样运行。请解释一下为什么这个 memoize 函数只有在我们使用：

f = memoize(f)

时才会应用到函数 f 上。

这个记忆化的代码来自于 edx.org 提供的 6.00x 在线课程。现在它无法运行，所以我来这里询问。

Answer 1

因为当你调用 fib2 的时候，它实际上是在调用一个没有使用缓存的原始版本。

return fib(n-1) + fib(n-2)

你只在第一次调用 fib2 时享受到装饰器的好处，而在后续的递归调用中，调用的都是普通的 fib 函数。

事情是这样的：

1. 当你调用 fib2 时，实际上是在调用 memf，
2. 如果参数不在缓存中（第一次调用时肯定不在），它会继续调用 fib，然后
3. fib 是递归的，它又会调用 fib。这不是装饰过的 fib2，所以后面的递归调用都没有使用缓存。

如果你再次用相同的参数调用 fib2，那时候结果会从缓存中返回，但你已经失去了大部分的好处。

你可以用以下方式创建装饰过的函数：

decorated = decorator(original)

但是因为你的函数是递归的，所以会遇到一些问题。

---

下面是一个示例。创建两个完全相同的 fib 函数，分别叫 fib_dec 和 fib_undec。修改装饰器，让它告诉你正在做什么：

def memoize(f): # Memoize a given function f
    def memf(*x):
        print("Memoized call.")
        if x not in memf.cache:
            print("Filling cache.")
            memf.cache[x] = f(*x)
        else:
            print("Cache retrieve.")
        return memf.cache[x]
    memf.cache = {}
    return memf

然后运行：

fib_dec = memoize(fib_dec) # fully memoized
fib_undec_1 = memoize(fib_undec) # not fully memoized

print("Calling fib_dec(2)")
print(fib_dec(2))
print("Calling fib_dec(1)")
print(fib_dec(1))
print("Calling fib_undec_1(2)")
print(fib_undec_1(2))
print("Calling fib_undec_1(1)")
print(fib_undec_1(1))
print("Calling fib_undec_1(2)")
print(fib_undec_1(2))

这将会得到：

Calling fib_dec(2) # fully decorated
Memoized call.
Filling cache.
Memoized call.
Filling cache.
Memoized call. # recusive calls all memoized
Filling cache.
2
Calling fib_dec(1)
Memoized call.
Cache retrieve. # previous recursive result cached
1
Calling fib_undec_1(2) # not fully memoized
Memoized call. # only one memoized call, recursion not memoized
Filling cache.
2
Calling fib_undec_1(1)
Memoized call.
Filling cache. # recursive result not cached
1
Calling fib_undec_1(2)
Memoized call.
Cache retrieve. # but original call is cached
2