Memoize装饰器无法记忆(当不使用装饰器语法时)

Question

我有一个简单的memoizer装饰器:

def funcmemo(f):
    memo = {}
    @wraps(f)
    def wrapper(*args):
    if args in memo:
        return memo[args]
    else:
        temp = f(*args)
        print "memoizing: ", args, temp  
        memo[args] = temp
        return temp
    return wrapper

现在,当我通过"@"令牌使用它时,

@funcmemo
def fib(n):
    print "fib called with:", n
    if n < 2: return n
    return fib(n-2) + fib(n-1)

res = fib(3)
print "result:", res

它正常工作,如打印输出中所示:

fib called with: 3
fib called with: 1
memoizing:  (1,) 1
fib called with: 2
fib called with: 0
memoizing:  (0,) 0
memoizing:  (2,) 1
memoizing:  (3,) 2
result:  2

但是,当我这样做时:

def fib(n):
    print "fib called with:", n
    if n < 2: return n
    return fib(n-2) + fib(n-1)

memfib = funcmemo(fib)
res = memfib(3)
print "result:", res

显然,一个未修饰的fib被调用,只有最终返回值"到达"缓存(显然导致巨大的减速):

fib called with: 3
fib called with: 1
fib called with: 2
fib called with: 0
fib called with: 1
memoizing:  (3,) 2
result: 2

奇怪的是,这个工作正常:

def fib(n):
    print "fib called with:", n
    if n < 2: return n
    return fib(n-2) + fib(n-1)

fib = funcmemo(fib)
res = fib(3)
print "result:", res

此外,基于类的版本也会发生同样的事情:

class Classmemo(object):
    def __init__ (self, f):
        self.f = f
        self.mem = {}
    def __call__ (self, *args):
        if args in self.mem:
            return self.mem[args]
        else:
            tmp = self.f(*args)
            print "memoizing: ", args, temp
            self.mem[args] = tmp
            return tmp

使用"匿名"装饰功能时也会出现问题

res = Classmemo(fib)(3)

我很高兴能够了解这背后的原因.

Answer 1

这没什么好奇的.当你这样做

memofib = funcmemo(fib)

您不是fib以任何方式更改功能点,而是创建新功能并将名称指向memofib它.

因此,当memofib被调用时,它调用名称指向的函数fib- 递归调用自身,而不是memofib- 因此不会发生任何记忆.

在你的第二个例子中,你做到了

fib = funcmemo(fib)

所以它以递归方式调用自己,并且所有级别都发生了memoization.

如果您不想覆盖名称fib,如装饰器版本或第二个示例所做的那样,您可以更改fib为采用函数名称:

def fib(n, fibfunc):
    print "fib called with:", n
    if n < 2: return n
    return fibfunc(n-2, fibfunc) + fibfunc(n-1, fibfunc)

memofib = funcmemo(fib)
res = fib(3, memofib)

您也可以使用固定点组合器来避免fibfunc每次都通过:

def Y(f):
    def Yf(*args):
        return f(Yf)(*args)
    return f(Yf)

@Y
def fib(f):
    def inner_fib(n):
        print "fib called with:", n
        if n < 2: return n
        return f(n-2) + f(n-1)
    return inner_fib