python - 记忆化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 的memoized 函数。当我们运行 fib2 时，它像普通的 fib 一样运行。请解释为什么这个 memoize 函数被应用于说一个函数 f 当且仅当我们使用:

f = memoize(f)

内存代码取自 6.00x a MOOC，由 edx.org 提供。它现在没有运行，这就是我来这里询问的原因。

Answer 1

因为当fib2递归调用

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

这是原始的、未memoized 的版本；您只会在第一次调用 fib2 时获得装饰器的好处，而不是所有对 vanilla fib 的递归调用。

这是发生了什么:

1. 当你调用fib2时，你实际上是在调用memf，它
2. 如果参数不在缓存中(因为它们不会在第一次调用时)，则依次调用 fib，然后
3. fib，递归 调用 fib。这不是修饰版fib2，因此所有其余的递归调用都不是memoized。

如果您使用相同的参数再次调用 fib2，将从缓存中返回，但您已经失去了大部分好处。

您可以一般使用以下方式创建修饰函数:

decorated = decorator(original)

但是由于你的函数被装饰是递归的，你会遇到问题。

---

下面是一个演示示例。创建两个相同的 fib 函数，fib_dec 和 fib_undec。修 retrofit 饰器以告诉您它在做什么:

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