记忆装饰器无法记忆（当不使用装饰器语法时） [英] Memoize decorators failing to memoize (when not using decorator syntax)

问题描述

我有一个简单的备忘录装饰器：

  def funcmemo（f）：
备忘录= {} 
 @wraps（f）
 def包装器（* args）：
如果备忘录中的args：
返回备忘录[args] 
其他：
 temp = f（* args）
 print memoizing：，args，temp 
 memo [args] = temp 
 return temp 
 return wrapper 
  

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

  @funcmemo 
 def fib（n）：
打印 fib call with：，n 
 if n ＜ 2：返回n 
返回fib（n-2）+ fib（n-1）
 
 res = fib（3）
打印结果：，res 
  

它可以正常工作，如打印输出所示：

< pre $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ FIB $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ f ：2
fib调用与：0
记录：（0，）0
记录：（2，）1
记录：（3，）2
结果： 2

但是，当我这样做时：

< pre $ = lang-py prettyprint-override> def fib（n）：
打印 fib call with：，n
如果n< 2：返回n
return fib（n-2）+ fib（n-1）

memfib = funcmemo（fib）
res = memfib（3）
打印结果：，res


显然，未修饰的纤维被调用，只有最终返回值到达缓存（显然会导致极大的减速）：

  fib调用为：3 
 fib调用时带有：1 
 fib调用时带有：2 
 fib调用时带有：0 
 fib调用时带有：1 
记录：（3，）2 
结果：2 
  

奇怪的是，这很好用：

  def fib（n）：
打印用以下命令调用的纤维，如果n< n，则
。 2：返回n 
 return fib（n-2）+ fib（n-1）
 
 fib = funcmemo（fib）
 res = fib（3）
打印结果：，res 
  

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

  class Classmemo（object）：
 def __init__（self，f）：
 self.f = f 
 self.mem = {} 
 def __call__（self，* args）：
如果self.mem中的args：
返回self.mem [args] 
 else：
 tmp = self.f（* args）
 print memoizing：，args，temp 
 self.mem [args] = tmp 
 return tmp 
  

使用匿名修饰功能（如

）时，也会发生此问题

  res = Classmemo（fib）（3）
  

我很高兴得知背后的原因。

解决方案

对此没有什么奇怪的。

  memofib = funcmemo（fib）
  

您不会以任何方式更改函数 fib 指向的位置，而是创建一个新功能，然后将名称指向 memofib 。

因此，当 memofib 被调用，它调用名称为 fib 指向的函数-递归地调用自身，而不是 memofib -这样就不会产生记忆。

在第二个示例中，您这样做

  fib = funcmemo（fib）
  

因此它以递归方式调用自己，并且在所有级别上都进行记忆

如果您不想覆盖名称 fib ，例如装饰器版本或第二个示例，您可以更改 fib 以使用函数名称：

  def fib （n，fibfunc）：
打印 fib with with：，如果n< n，则
。 2：返回n 
返回fibfunc（n-2，fibfunc）+ fibfunc（n-1，fibfunc）
 
 memofib = funcmemo（fib）
 res = fib（3， memofib）
  

您也可以使用定点组合器，以避免每次都通过 fibfunc ：

  def Y（f）：
 def Yf（* args）：
返回f（Yf）（* args）
返回f（Yf）
 
 @Y 
 def fib（f）：
 def inner_fib（n）：
打印 fib with with：，n $ b如果n< $ b 2：返回n 
返回f（n-2）+ f（n-1）
返回inner_fib 
  

I've got a simple memoizer decorator:

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

Now, when I use it via the "@" token,

@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

it works correctly, as seen in the printed output:

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

However, when I do this:

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

Apparently an undecorated fib gets called, with only the final return value "reaching" the cache (obviously resulting in huge slowdown):

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

Curiously, this one works fine:

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

Also, the very same thing happens with a class-based version:

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

The problem also occurs when using an "anonymous" decorated function, like

res = Classmemo(fib)(3)

I'd be glad to be enlightened about the reasons behind this.

解决方案

There is nothing curious about this. When you do

memofib = funcmemo(fib)

You're not changing the function fib points to in any way, but creating a new function and pointing the name memofib at it.

So when memofib gets called, it calls the function pointed to by the name fib -- which recursively calls itself, not memofib -- so no memoization occurs.

In your second example, you do

fib = funcmemo(fib)

so it calls itself recursively and memoization happens at all levels.

If you don't want to overwrite the name fib, as the decorator version or your second example does, you could alter fib to take a function name:

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)

You could also use a fixed point combinator to avoid passing fibfunc every time:

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

这篇关于记忆装饰器无法记忆（当不使用装饰器语法时）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！