2道極好的Python算法題|帶你透徹理解裝飾器的妙用
前一篇講了裝飾器額基本知識，裝飾器我個人認為是Python中最最最難的知識點 ，上一篇算是一個入門的介紹，有18個小伙伴給我留言，后臺也有很多同學跟我討論，大家總是覺得不過癮，好像離深入理解還差那么一丟丟趕腳，裝飾器到底有啥妙用呢,其實裝飾器內容非常豐富， 今天我分享兩道非常好的算法題，大家耐心看完兩道算法題之后 ， 注意精華在最后，我相信大家對裝飾器的理解又會更上一層樓 .
1.斐波那契數列
1).這個序列非常有名，我非常喜歡這個序列(有同學問我為啥，偷偷告訴大家，這個序列幫了我不少忙,等下半年我寫數據分析文章的時候，會跟大家分享心得)
這個序列也叫兔子序列，網上有很多關于這個序列的解法，我們就直接上代碼
我們用推導列表把兔子序列前10項打印出來,有同學說這個跟裝飾器有毛關系，不要急，如果我們若打印40項，看看需要花多少時間
import time
start=time.time()
[fib(n) for n in range(40)]
end=time.time()
print 'cost:{}'.format(end-start)
>>
cost:150.200000048
如果我們打印50項，則需要花更多的時間，光40項需要花150多秒,50項就更長了.難是因為這個運算量太大了嗎,NONONO,是因為我們算法沒有經過優化.
-
看上面這張圖，你會發現我們在計算兔子序列的時候，有大量重復的計算，比如算F(10)=F(9)+F(8),F(9)=F(8)+F(7),F(8)需要重復計算兩次~~
-
怎么破，很容易想到我們需要用一個緩存，把這個計算過的數字存在一個表里面，用的時候若這個數字在這個表，就不用再花cpu去運算，直接取就好了。
2).先把上面的代碼改一下,我們申明一個count變量，每次遞歸都存起來，然后最后再返回
3).接著演變，我們現在構造一個緩沖區cache
我們查表，比如用字典來保存，比如cache[8]=34,我們只需要查一下8是不是在字典里面就可以了，在的話直接取，不在的話再去用算法計算，是不是很爽
看運行40項，幾乎不費吹灰之力，非常快
2.爬樓梯
比如我有7階臺階，我們可以用兩種爬發，一次一步或者兩步，只能進不能退，算算有多少種爬法
我們先簡單分析一下：
-
若只有一階臺階，那么不管是一次選擇一步還是兩步，都只有一種爬法
-
若只有兩階臺階，選擇一步or兩步，會有兩種爬法
-
若只有三階臺階，選擇一步然后一步然后一步，或者一步，兩步，或者兩步，一步，這樣有3種爬法
-
若只有四階臺階，選擇一步，然后剩下3階臺階的爬法，這3階爬法可以直接取前面3階臺階的計算結果
我們先寫源碼，源碼很簡單用遞歸搞定，首先設計遞歸的出口,當只有1階或者小于1階臺階時候，直接return 1
大家有沒有發現這個爬樓梯一樣存在重復計算的問題,比如5階的時候，一步一步然后剩下3步，或者兩步然后剩下3步
一樣需要用到兔子序列的cache方法，那么在climb函數中再重復寫一篇，是不是很累贅，這不是Pythonic的風格，有沒有比較好的封裝方法呢，同時又能不改動原始的代碼呢～～ 有的，牛逼閃閃的Python當然有，就是我們的裝飾器啦, 好我們看裝飾器如何封裝搞定
3.裝飾器封裝
對于兔子序列和爬樓梯，我們用裝飾器去封裝一下，怎么封裝呢，我們一步一步來,參考上一篇入門很容易構建出來
1).創建一個裝飾器
def decorate(func):
cache={}
def wrap(n):
if n not in cache:
cache[n]=func(n)
return cache[n]
return wrap
2).裝飾一下斐波那契數列
是不是很簡潔，裝飾器真是個好東西啊~~
3).裝飾器參數升級
大家有沒有發現我們上面構造的裝飾器，入參是一個參數n.如果碰到需要傳入的多個參數的函數怎么辦， 比如我們的爬樓梯原函數就是2個參數， 所以我們需要把裝飾器寫更通俗一點，對用變參
留幾個問題:
1.print climb(5,(1,2))為啥不是[1,2]
2.為啥不能加else
def decorator(func):
cache={}
def wrap(*args):
if args not in cache:
cache[args]=func(*args)
else:
return cache[args]
return wrap
3.加緩沖的時候
def fib(n，cache=None):
為啥不能寫成def fib(n，cache={}):
好了 裝飾器的妙用就講到這里, 大家想一想如果我們還有類似的代碼需要緩存機制，是不是只需要用裝飾器封裝一下就行了，是不是代碼簡潔很多而且容易維護和擴展功能，講到這里 大家是不是對裝飾器的妙用有了進一步的理解 ,若有什么不懂的,也可以留言跟我探討交流
來自：https://zhuanlan.zhihu.com/p/26151166