首頁  >  文章  >  後端開發  >  Python中使用裝飾器來優化尾遞歸

Python中使用裝飾器來優化尾遞歸

高洛峰
高洛峰原創
2017-03-02 10:55:031672瀏覽

這裡我們用典型的斐波那契數列作為例子,來展示Python中使用裝飾器來優化尾遞歸的範例,需要的朋友可以參考下

尾遞歸簡介
尾遞歸是函數傳回最後一個操作是遞歸調用,則該函數是尾遞歸。
遞歸是線性的例如factorial函數每一次呼叫都會創建一個新的棧(last-in-first-out)透過不斷的壓棧,來創建遞歸, 很容易導致棧的溢出。而尾遞歸則使用目前堆疊透過資料覆蓋來最佳化遞歸函數。
階乘函數factorial, 透過把計算值傳遞的方法完成了尾遞歸。但python不支出編譯器優化尾遞歸所以當遞歸多次的話還是會報錯(學習用)。

eg:

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

print factorial(5, 1) # 120

#尾遞歸最佳化##這裡用到了斐波那契數來當例子.線性遞歸的演算法由於太過一低效就被我們Pass掉了,我們先來看尾遞過方式的呼叫:

(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),也能在780ms跑出結果(780ms是以前博文提到那台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&#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

使用的方法前面已經展示了,令我感到大開眼界的是,作者用了拋出異常然後自己捕獲的方式來打破調用棧的增長,簡直是太匪夷所思了。而且效率問題,和直接尾遞歸Fib相比大概造成了五倍的時間開銷。

最後很不可思議的,尾遞歸優化的目的達成了。


更多Python中使用裝飾器來優化尾遞歸相關文章請關注PHP中文網!


陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn