记忆化Python函数

这是一小段代码，它将每个函数转换为其记忆版本。

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不是一个memoized 函数fib。当我们跑步时fib2它就像普通的谎言一样。请解释为什么会这样memoize函数被应用来表示一个函数f当且仅当我们使用：

f = memoize(f)

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

因为当fib2递归调用

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

这是原来的，非memoized 版本；您只有在第一次调用时才能获得装饰器的好处fib2，并非所有对普通的递归调用fib.

发生的情况如下：

1. 你打电话时fib2，你真的在​​打电话memf, which
2. calls fib反过来，如果参数不在缓存中（因为它们不会在第一次调用时），那么
3. fib，递归calls fib。这是not装饰版fib2，所以所有其余的递归调用都没有被memoized.

如果你打电话fib2再次以相同的论点，will从缓存中返回，但你已经失去了大部分好处。

您可以创建装饰函数一般来说 using:

decorated = decorator(original)

但随着你的功能被装饰是递归的，你遇到了问题。

下面是一个演示示例。创建两个相同的fib功能，fib_dec and 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