Utiliser des décorateurs pour optimiser la récursivité de la queue en Python

Ici, nous utilisons la séquence typique de Fibonacci comme exemple pour montrer comment utiliser les décorateurs pour optimiser la récursion de la queue en Python. Les amis dans le besoin peuvent se référer à

Introduction à la récursion de la queue
La récursion de queue signifie que la dernière opération renvoyée par la fonction est un appel récursif, alors la fonction est récursive de queue. La récursion est linéaire. Par exemple, chaque fois que la fonction factorielle est appelée, une nouvelle pile (dernier entré, premier sorti) est créée en poussant continuellement la pile, ce qui peut facilement conduire à un débordement de pile. La récursion de queue utilise la pile actuelle pour optimiser les fonctions récursives grâce à la couverture des données.
La fonction factorielle factorielle complète la récursivité de la queue en transmettant la valeur calculée. Cependant, Python ne permet pas au compilateur d'optimiser la récursion de queue, donc si la récursion est répétée plusieurs fois, une erreur sera toujours signalée (à des fins d'apprentissage).

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

print factorial(5, 1) # 120

L'optimisation récursive de queue est utilisée ici Les nombres de Fibonacci sont utilisés comme exemple. L'algorithme récursif linéaire a été adopté par nous car il était trop inefficace. Examinons d'abord la méthode d'appel par passe finale :

(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)

Testons ce programme et appelons Fib(1001 ). Le résultat est :

>>> 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

>>>

Si nous utilisons Fib(1002 ), le le résultat est la table basse, comme suit :

 .....

 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

>>>

Bon, maintenant nous arrivons à l'optimisation récursive

Nous donnons juste au Fib maintenant La fonction ajoute un Décorateur, comme suit :

@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)

Maintenant, même si nous utilisons Fib (20000), nous pouvons exécuter le résultat en 780 ms (780 ms est le résultat du netbook à 2000 yuans mentionné dans le billet de blog précédent)

Ce n'est pas un mensonge , Jetons un coup d'œil à ce code magique :

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'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

La méthode utilisée a déjà été montrée, ce qui me révèle une révélation. Oui, l'auteur a utilisé la méthode consistant à lancer des exceptions puis à les attraper lui-même pour interrompre la croissance de la pile d'appels, ce qui est tout simplement incroyable. De plus, les problèmes d’efficacité entraînent environ cinq fois plus de temps que la récursion directe de la queue Fib.

Au final, étonnamment, l'objectif d'optimisation de la récursivité de la queue a été atteint.

Pour plus d'articles sur l'utilisation de décorateurs pour optimiser la récursivité de la queue en Python, veuillez faire attention au site Web PHP chinois !