Verständnis eines memoization Dekorateur als Verschluss

Question

Ich versuche, über Python Dekorateure zu lernen, und ich möchte genau im Detail verstehen, wie Verschluss, beispielsweise in diesem memoization Zusammenhang gilt:

def memoize(f): 
    memo = {} 
    def helper(x):     
     if x not in memo: 
      memo[x] = f(x) 
     return memo[x] 
    return helper 

@memoize 
def fib(n): 
    if n in (0,1): 
     return n 
    return fib(n - 1) + fib(n - 2) 

I verstehen, dass memoize Funktionen zurückgibt, die an memo Werte im umschließenden Bereich helper gebunden sind, auch wenn der Programmablauf nicht mehr in diesem umschließenden Bereich ist. Wenn also memoize wiederholt aufgerufen wird, wird eine variierende Folge von Funktionen zurückgegeben, abhängig von den aktuellen Werten von memo. Ich verstehe auch, dass @memoize ist syntaktischer Zucker, der Aufrufe an fib(n) durch Aufrufe an memoize(fib(n)) ersetzt wird.

Wo ich zu kämpfen habe ist, wie der genannte Wert von n in fib(n) wirksam auf die x in helper(x) umgewandelt wird. Die meisten Tutorials zu Schließungen scheinen diesen Punkt nicht explizit zu machen, oder sie sagen eher vage, dass eine Funktion sich über die andere schließt, was sie nur magisch klingen lässt. Ich kann sehen, wie man die Syntax benutzt, möchte aber besser verstehen, was genau hier passiert und welche Objekte und Daten beim Ausführen des Codes weitergegeben werden.

Answer 1

Sie haben missverstanden, was der @memoize Dekorateur tut. Der Decorator wird nicht jedes Mal aufgerufen, wenn Sie fib aufrufen. Der Dekorateur heißt nur einmal pro Funktion, die dekoriert ist.

Die ursprüngliche fib Funktion ist ersetzt durch die helper() Funktion, mit dem ursprünglichen Funktion Objekt zur Verfügung als f Verschluss zusammen mit der memo Schließung:

>>> def fib(n): 
...  if n in (0,1): 
...   return n 
...  return fib(n - 1) + fib(n - 2) 
... 
>>> fib 
<function fib at 0x1023398c0> 
>>> memoize(fib) 
<function helper at 0x102339758> 

Dies gibt den Ersatz helper Funktion eine Schließung, und jedes Mal, wenn Sie diese helper() Funktion aufrufen das gleiche memo Wörterbuch wird verwendet, um bereits produzierte Ergebnisse für den aktuellen Wert von x nachschlagen.

Sie können dies alle Arbeiten im Interpreter sehen:

>>> @memoize 
... def fib(n): 
...  if n in (0,1): 
...   return n 
...  return fib(n - 1) + fib(n - 2) 
... 
>>> fib 
<function helper at 0x10232ae60> 

Hinweis der Name der Funktion dort! Das ist helper. Es hat einen Verschluss:

>>> fib.__closure__ 
(<cell at 0x10232d9f0: function object at 0x10232ade8>, <cell at 0x10232da98: dict object at 0x102353050>) 

ein Funktionsobjekt und ein Wörterbuch, das ist f und memo ist. Besuchen Sie den Zellinhalt mit .cell_contents:

>>> fib.__closure__[0].cell_contents 
<function fib at 0x10232ade8> 
>>> fib.__closure__[1].cell_contents 
{} 

Das ist die ursprüngliche dekoriert Funktion und das leere Wörterbuch in Ordnung. Lassen Sie sich diese Funktion nutzen:

>>> fib(0) 
0 
>>> fib(1) 
1 
>>> fib.__closure__[1].cell_contents 
{0: 0, 1: 1} 

, dass die resultierenden Werte für x-Set zu 0 und 1 im memo Wörterbuch gespeichert werden. Das nächste Mal, wenn ich fib mit beiden Wert aufrufen, wird das Memo verwendet.Neue x Werte werden berechnet und hinzugefügt:

>>> fib(2) 
1 
>>> fib.__closure__[1].cell_contents 
{0: 0, 1: 1, 2: 1} 

Sie sehen können, wie gut die durch Timing, wie lange eine größere Anzahl arbeitet zu berechnen nimmt:

>>> start = time.clock(); fib(500); print(format(time.clock() - start, '.10f')) 
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L 
0.0008390000 
>>> start = time.clock(); fib(500); print(format(time.clock() - start, '.10f')) 
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L 
0.0000220000 

>>> start = time.clock(); fib(500); print(format(time.clock() - start, '.10f')) 
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L 
0.0000190000 

Nach dem ersten Aufruf wird das memo aufzublicken ist 40 Mal so schnell wie alle Zwischenergebnisse protokolliert wurden: