Verwendung von Dekoratoren zur Optimierung der Schwanzrekursion in Python-Python-Tutorial-php.cn

Verwendung von Dekoratoren zur Optimierung der Schwanzrekursion in Python

高洛峰

Freigeben： 2017-03-02 10:55:03

Original

1689 Leute haben es durchsucht

Hier verwenden wir die typische Fibonacci-Sequenz als Beispiel, um zu zeigen, wie Dekoratoren zur Optimierung der Schwanzrekursion in Python verwendet werden. Freunde in Not können sich auf

Einführung in die Schwanzrekursion
Tail-Rekursion bedeutet, dass die letzte von der Funktion zurückgegebene Operation ein rekursiver Aufruf ist und die Funktion dann tail-rekursiv ist. Rekursion ist linear. Jedes Mal, wenn die Fakultätsfunktion aufgerufen wird, wird ein neuer Stapel (Last-In-First-Out) erstellt, indem der Stapel kontinuierlich verschoben wird, was leicht zu einem Stapelüberlauf führen kann. Die Schwanzrekursion nutzt den aktuellen Stapel, um rekursive Funktionen durch Datenabdeckung zu optimieren.
Die Fakultätsfunktion „Fakultät“ schließt die Schwanzrekursion ab, indem sie den berechneten Wert übergibt. Allerdings erlaubt Python dem Compiler nicht, die Schwanzrekursion zu optimieren. Wenn die Rekursion also mehrmals wiederholt wird, wird immer noch ein Fehler gemeldet (zu Lernzwecken).

zB:

def factorial(n, x):
  if n == 0:
    return x
  else:
    return factorial(n-1, n*x)

print factorial(5, 1) # 120

Nach dem Login kopieren

Tail Recursive Optimization wird hier verwendet Als Beispiel wird der lineare rekursive Algorithmus verwendet, weil er zu ineffizient war. Schauen wir uns zunächst die Tail-Pass-Aufrufmethode an:

(n,b1=1,b2=1,c=3):
 if n<3:
  return 1
 else:
  if n==c:
   return b1+b2
  else:
   return Fib(n,b1=b2,b2=b1+b2,c=c+1)

Nach dem Login kopieren

Lassen Sie uns dieses Programm testen und Fib(1001) aufrufen. Das Ergebnis ist:

>>> def Fib(n,b1=1,b2=1,c=3):

...  if n<3:

...   return 1

...  else:

...   if n==c:

...    return b1+b2

...   else:

...    return Fib(n,b1=b2,b2=b1+b2,c=c+1)

... 

>>> Fib(1001)

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501L

>>>

Nach dem Login kopieren

Wenn wir Fib(1002) verwenden, ist das Ergebnis Das Ergebnis ist die Kaffeetabelle wie folgt:

 .....

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

 File "<stdin>", line 8, in Fib

RuntimeError: maximum recursion depth exceeded

>>>

Nach dem Login kopieren

Okay, jetzt kommen wir zur Tail-rekursiven Optimierung

Wir geben die Fib einfach Jetzt fügt die Funktion einen Dekorator wie folgt hinzu:

@tail_call_optimized
def Fib(n,b1=1,b2=1,c=3):
 if n<3:
  return 1
 else:
  if n==c:
   return b1+b2
  else:
   return Fib(n,b1=b2,b2=b1+b2,c=c+1)

Nach dem Login kopieren

Nun, es ist dieser @tail_call_optimized-Dekorator, dieser Dekorator macht Python magisch Es durchbricht die Grenze des Aufrufstapels.

Selbst wenn wir Fib (20000) verwenden, können wir das Ergebnis in 780 ms ausführen (780 ms ist das Ergebnis des im vorherigen Blogbeitrag erwähnten 2000-Yuan-Netbooks)

Das ist keine Lüge Schauen wir uns diesen magischen Code an:

class TailRecurseException: 
 def __init__(self, args, kwargs): 
 self.args = args 
 self.kwargs = kwargs 
 
def tail_call_optimized(g): 
 """ 
 This function decorates a function with tail call 
 optimization. It does this by throwing an exception 
 if it is it&#39;s own grandparent, and catching such 
 exceptions to fake the tail call optimization. 
 
 This function fails if the decorated 
 function recurses in a non-tail context. 
 """ 
 def func(*args, **kwargs): 
 f = sys._getframe() 
 if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code: 
  raise TailRecurseException(args, kwargs) 
 else: 
  while 1: 
  try: 
   return g(*args, **kwargs) 
  except TailRecurseException, e: 
   args = e.args 
   kwargs = e.kwargs 
 func.__doc__ = g.__doc__ 
 return func

Nach dem Login kopieren

Die verwendete Methode wurde bereits zuvor gezeigt, was mir die Augen öffnet. Ja, der Autor hat die Methode verwendet, Ausnahmen auszulösen und sie dann selbst abzufangen, um das Wachstum des Aufrufstapels zu stoppen, was einfach unglaublich ist. Darüber hinaus verursachen Effizienzprobleme etwa den fünffachen Zeitaufwand im Vergleich zu Fib mit direkter Tail-Rekursion.

Am Ende wurde überraschenderweise das Ziel der Schwanzrekursionsoptimierung erreicht.

Weitere Artikel zur Verwendung von Dekoratoren zur Optimierung der Schwanzrekursion in Python finden Sie auf der chinesischen PHP-Website!