记忆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返回第nth Fibonacci 数：

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它就像普通的 fib 一样运行。请解释为什么当且仅当我们使用这个memoize函数来表示一个函数f时：

f = memoize(f)

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

Answer 1

因为当fib2递归调用

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

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

这是发生的事情：

1. 当你打电话时fib2，你真的在​​打电话memf，
2. 调用fib反过来，如果参数不在缓存中（因为他们不会在第一次调用），然后
3. fib，被递归调用fib。这不是装饰版本fib2，因此所有其余的递归调用都不是memoized。

如果您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