Python中使用裝飾器來優(yōu)化尾遞歸的示例
尾遞歸簡介
尾遞歸是函數返回最后一個操作是遞歸調用,則該函數是尾遞歸。
遞歸是線性的比如factorial函數每一次調用都會創(chuàng)建一個新的棧(last-in-first-out)通過不斷的壓棧,來創(chuàng)建遞歸, 很容易導致棧的溢出。而尾遞歸則使用當前棧通過數據覆蓋來優(yōu)化遞歸函數。
階乘函數factorial, 通過把計算值傳遞的方法完成了尾遞歸。但是python不支出編譯器優(yōu)化尾遞歸所以當遞歸多次的話還是會報錯(學習用)。
eg:
def factorial(n, x): if n == 0: return x else: return factorial(n-1, n*x) print factorial(5, 1) # 120
尾遞歸優(yōu)化
這里用到了斐波那契數來作為例子.線性遞歸的算法由于太過一低效就被我們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 >>>
好了,現在我們來尾遞歸優(yōu)化
我們給剛才的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'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相比大概造成了五倍的時間開銷。
最后很不可思議的,尾遞歸優(yōu)化的目的達成了。
相關文章
淺談Python中threading join和setDaemon用法及區(qū)別說明
這篇文章主要介紹了淺談Python中threading join和setDaemon用法及區(qū)別說明,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-05-05python tkinter控件treeview的數據列表顯示的實現示例
本文主要介紹了python tkinter控件treeview的數據列表顯示的實現示例,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-01-01