memoize的裝飾未能memoize的（不使用修飾語法時）

我有一個簡單的memoizer裝飾：memoize的裝飾未能memoize的（不使用修飾語法時）

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)

我會很高興得到啓發關於這背後的原因也發生

的問題。

來源

2012-03-22 András Kovács

是的，你是對的。但你的問題在哪裏？ – Alfe 2012-03-22 09:54:43

對此沒有什麼好奇的。當你做

memofib = funcmemo(fib)

你不改變功能fib點以任何方式，但創建一個新功能和指向它的名字memofib。

所以當memofib被調用，它調用的函數的名稱爲fib指出 - 這遞歸調用本身，而不是memofib - 所以不會發生記憶化。

在你的第二個例子，你做

fib = funcmemo(fib)

所以遞歸調用自己和記憶化發生在各個層面。

如果你不希望覆蓋名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)

你也可以使用一個fixed point combinator來避免將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

來源

2012-03-22 09:48:08 agf

我明白了..謝謝。 – 2012-03-22 09:59:17

另外，感謝設置我通過提出固定點組合器完成大腦崩潰的課程。 – 2012-03-22 12:32:00

@AndrásKovács我無法抗拒:)。只要我輸入了傳遞函數的版本，我意識到這可能是我唯一能夠在問題中沒有具體提及的時候使用的。 – agf 2012-03-22 12:36:06

如果你的問題只是一個簡單的爲什麼，我想答案是僅僅因爲recu與fib()進行的rsion-call調用名稱爲fib()的函數。要裝飾你必須替換指針的值fib;這不是由memfib = funcmemo(fib)也不是由類版本完成的。

來源

2012-03-22 09:59:29 Alfe

memoize的裝飾未能memoize的（不使用修飾語法時）

回答

相關問題