欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python中使用裝飾器來優(yōu)化尾遞歸的示例

 更新時(shí)間:2016年06月18日 14:59:13   作者:cangmean  
這里我們用典型的斐波那契數(shù)列作為例子,來展示Python中使用裝飾器來優(yōu)化尾遞歸的示例,需要的朋友可以參考下

尾遞歸簡介
尾遞歸是函數(shù)返回最后一個(gè)操作是遞歸調(diào)用,則該函數(shù)是尾遞歸。
遞歸是線性的比如factorial函數(shù)每一次調(diào)用都會(huì)創(chuàng)建一個(gè)新的棧(last-in-first-out)通過不斷的壓棧,來創(chuàng)建遞歸, 很容易導(dǎo)致棧的溢出。而尾遞歸則使用當(dāng)前棧通過數(shù)據(jù)覆蓋來優(yōu)化遞歸函數(shù)。
階乘函數(shù)factorial, 通過把計(jì)算值傳遞的方法完成了尾遞歸。但是python不支出編譯器優(yōu)化尾遞歸所以當(dāng)遞歸多次的話還是會(huì)報(bào)錯(cuò)(學(xué)習(xí)用)。

eg:

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

print factorial(5, 1) # 120

尾遞歸優(yōu)化
這里用到了斐波那契數(shù)來作為例子.線性遞歸的算法由于太過一低效就被我們Pass掉了,我們先來看尾遞過方式的調(diào)用:

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

這段程序我們來測試一下,調(diào)用 Fib(1001)結(jié)果:

>>> 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),結(jié)果,茶幾了,如下:

 .....

 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

>>> 

好了,現(xiàn)在我們來尾遞歸優(yōu)化

我們給剛才的Fib函數(shù)增加一個(gè)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)

 
恩,就是這個(gè)@tail_call_optimized的裝飾器 ,這個(gè)裝飾器使Python神奇的打破了調(diào)用棧的限制。

這下即使我們Fib(20000),也能在780ms跑出結(jié)果(780ms是以前博文提到那臺(tái)2000元的上網(wǎng)本跑出來的結(jié)果)

不賣關(guān)子了,下面我們來看看這段神奇的代碼: 

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

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

最后很不可思議的,尾遞歸優(yōu)化的目的達(dá)成了。

相關(guān)文章

  • Python自動(dòng)創(chuàng)建Excel并獲取內(nèi)容

    Python自動(dòng)創(chuàng)建Excel并獲取內(nèi)容

    這篇文章主要介紹了Python自動(dòng)創(chuàng)建Excel并獲取內(nèi)容,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-09-09
  • 淺談Python中threading join和setDaemon用法及區(qū)別說明

    淺談Python中threading join和setDaemon用法及區(qū)別說明

    這篇文章主要介紹了淺談Python中threading join和setDaemon用法及區(qū)別說明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2020-05-05
  • Python實(shí)現(xiàn)的括號(hào)匹配判斷功能示例

    Python實(shí)現(xiàn)的括號(hào)匹配判斷功能示例

    這篇文章主要介紹了Python實(shí)現(xiàn)的括號(hào)匹配判斷功能,涉及Python棧與列表的存儲(chǔ)、遍歷、判斷等相關(guān)操作技巧,需要的朋友可以參考下
    2018-08-08
  • 自己使用總結(jié)Python程序代碼片段

    自己使用總結(jié)Python程序代碼片段

    這篇文章主要介紹了自己使用總結(jié)Python程序代碼片段,本文收集了如反向讀取文件、往文件中所有添加指定的前綴、匿名函數(shù)作為返回值、將二進(jìn)制數(shù)轉(zhuǎn)為10進(jìn)制數(shù)等實(shí)用代碼片段,需要的朋友可以參考下
    2015-06-06
  • python的rllib庫你了解嗎

    python的rllib庫你了解嗎

    這篇文章主要介紹了python urllib庫的使用,幫助大家更好的利用python學(xué)習(xí)爬蟲,感興趣的朋友可以了解下,希望能夠給你帶來幫助
    2021-11-11
  • Python如何實(shí)現(xiàn)遠(yuǎn)程方法調(diào)用

    Python如何實(shí)現(xiàn)遠(yuǎn)程方法調(diào)用

    這篇文章主要介紹了Python如何實(shí)現(xiàn)遠(yuǎn)程方法調(diào)用,文中講解非常細(xì)致,幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下
    2020-08-08
  • python繪制分布折線圖的示例

    python繪制分布折線圖的示例

    這篇文章主要介紹了python繪制分布折線圖的示例代碼,幫助大家更好的利用python繪制圖像,感興趣的朋友可以了解下
    2020-09-09
  • Python中subprocess模塊的用法詳解

    Python中subprocess模塊的用法詳解

    這篇文章主要介紹了Python中subprocess模塊的用法詳解,subprocess是Python 2.4中新增的一個(gè)模塊,它允許你生成新的進(jìn)程,連接到它們的 input/output/error 管道,并獲取它們的返回狀態(tài)碼,這個(gè)模塊的目的在于替換幾個(gè)舊的模塊和方法,需要的朋友可以參考下
    2023-08-08
  • python tkinter控件treeview的數(shù)據(jù)列表顯示的實(shí)現(xiàn)示例

    python tkinter控件treeview的數(shù)據(jù)列表顯示的實(shí)現(xiàn)示例

    本文主要介紹了python tkinter控件treeview的數(shù)據(jù)列表顯示的實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-01-01
  • 利用Python查看目錄中的文件示例詳解

    利用Python查看目錄中的文件示例詳解

    這篇文章主要給大家介紹了關(guān)于利用Python查看目錄中的文件,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面跟著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2017-08-08

最新評(píng)論