デコレータを使用して Python で末尾再帰を最適化する

ここでは、例として典型的なフィボナッチ数列を使用して、デコレーターを使用して Python で末尾再帰を最適化する方法を示します。必要な方は、

末尾再帰の概要
末尾再帰とは、関数が最後の操作を返すときのことです。が再帰呼び出しである場合、関数は末尾再帰です。
再帰は線形です。たとえば、階乗関数が呼び出されるたびに新しいスタック (後入れ先出し) が作成され、スタックを継続的にプッシュすることで再帰が発生し、スタック オーバーフローが発生しやすくなります。末尾再帰は、現在のスタックを使用して、データ カバレッジを通じて再帰関数を最適化します。
階乗関数factorialは、計算された値を渡すことによって末尾再帰を完了します。ただし、Python ではコンパイラーが末尾再帰を最適化できないため、再帰が複数回繰り返された場合でも、(学習目的で) エラーが報告されます。

例:

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

print factorial(5, 1) # 120

末尾再帰最適化
線形再帰アルゴリズムは非効率すぎるため、ここでは例として使用されています。まず、 の呼び出しを見てみましょう。テールパスメソッド:

(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) を呼び出してみましょう。結果は次のようになります:

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

>>>

Fib(1002) を使用すると、結果はコーヒーテーブルになります。

 .....

 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

>>>

さて、末尾再帰最適化に移ります

今、次のように Fib 関数に Decorator を追加します:

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

さて、これは@tail_call_optimized の装飾 このデコレーターにより、Python は呼び出しスタックの制限を魔法のように突破できます。

これで、Fib (20000) を使用した場合でも、結果を 780 ミリ秒で実行できます (780 ミリ秒は、前のブログ投稿で言及した 2000 元のネットブックの結果です)

早速、この魔法のコードを見てみましょう。 :

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

が使用したメソッドは、以前にも紹介しましたが、著者が例外をスローし、それを自分でキャッチして呼び出しスタックの増大を阻止するというメソッドを使用したことです。ただただ信じられないほどです。さらに、効率の問題により、直接末尾再帰 Fib と比較して約 5 倍の時間オーバーヘッドが発生します。

最終的には、驚くべきことに、末尾再帰最適化の目標は達成されました。

Python での末尾再帰を最適化するためのデコレーターの使用に関連するその他の記事については、PHP 中国語 Web サイトに注目してください。