记忆化python函数 [英] Memoization python function

问题描述

这是一小段代码，可以将每个函数转换为其备注版本.

Here's a little piece of code which converts every function to its memoization version.

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 个斐波那契数:

For instance, if we have a function fib as follows which returns the nth Fibonacci number:

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

现在，可以使用来记住以上功能

Now, the above function can be memoized by using

fib = memoize(fib)

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

Everything is fine up to this point but what I can't understand is that if we do something like this, instead of:

fib = memoize(fib)

我们改为:

fib2 = memoize(fib)

函数 fib2 不是 fib 的 memoize d函数.当我们运行 fib2 时，它的运行方式类似于普通的fib.请解释为什么仅当我们使用以下情况时，为什么将此 memoize 函数应用为函数 f :

the function fib2 isn't a memoized function of fib. When we run fib2 it runs like ordinary fib. Please explain why this memoize function gets applied to say a function f if and only if we use:

f = memoize(f)

该备忘录代码取自edx.org提供的MOOC的6.00倍.现在还没有运行，这就是为什么我来这里问问题的原因.

The memoization code is taken from 6.00x a MOOC provided by edx.org. It's not running right now that's why I have come here to ask.

推荐答案

因为 fib2 递归调用

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

是原始的，未存储的原始版本.您只会在第一次调用 fib2 时获得装饰器的好处，而不是对香草 fib 的所有递归调用.

that is the original, un-memoized version; you only get the benefit of the decorator on the first call to fib2, not all the recursive calls to vanilla fib.

发生的事情是这样:

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

1. When you call fib2, you are really calling memf, which
2. calls fib in turn if the arguments aren't in the cache (as they won't be on the first call), then
3. fib, being recursive calls fib. This is not the decorated version fib2, so all of the rest of the recursive calls aren't being memoized.

如果再次使用相同的参数调用 fib2 ，则会从缓存中返回 ，但是您失去了大部分好处.

If you call fib2 again with the same arguments, that will be returned from the cache, but you have lost most of the benefit.

您可以使用以下方法来创建修饰的功能 :

You can create decorated functions in general using:

decorated = decorator(original)

但是由于要修饰的函数是递归，因此您会遇到问题.

but as your function being decorated is recursive, you run into problems.

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

Below is a demo example. Create two identical fib functions, fib_dec and fib_undec. Modify the decorator to tell you what it's doing:

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

这篇关于记忆化python函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！