2道极好的Python算法题|带你透彻理解装饰器的妙用

Jac9737 2年前
   <p style="text-align:center"><img src="https://simg.open-open.com/show/ec4db183560c556c5fae6ac5c3f2958e.jpg"></p>    <p>前一篇讲了装饰器额基本知识,装饰器我个人认为是Python中最最最难的知识点 ,上一篇算是一个入门的介绍,有18个小伙伴给我留言,后台也有很多同学跟我讨论,大家总是觉得不过瘾,好像离深入理解还差那么一丢丢赶脚,装饰器到底有啥妙用呢,其实装饰器内容非常丰富, 今天我分享两道非常好的算法题,大家耐心看完两道算法题之后 , 注意精华在最后,我相信大家对装饰器的理解又会更上一层楼 .</p>    <p>1.斐波那契数列</p>    <p>1).这个序列非常有名,我非常喜欢这个序列(有同学问我为啥,偷偷告诉大家,这个序列帮了我不少忙,等下半年我写数据分析文章的时候,会跟大家分享心得)</p>    <p>这个序列也叫兔子序列,网上有很多关于这个序列的解法,我们就直接上代码</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/960e3fd73a61a5a1a489e57322738101.png"></p>    <p>我们用推导列表把兔子序列前10项打印出来,有同学说这个跟装饰器有毛关系,不要急,如果我们若打印40项,看看需要花多少时间</p>    <pre>  <code class="language-python">import time   start=time.time()  [fib(n) for n in range(40)]  end=time.time()  print 'cost:{}'.format(end-start)  >>  cost:150.200000048</code></pre>    <p>如果我们打印50项,则需要花更多的时间,光40项需要花150多秒,50项就更长了.难是因为这个运算量太大了吗,NONONO,是因为我们算法没有经过优化.</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/3e6dabe5e87c7e386377e592f077ee63.png"></p>    <ul>     <li> <p>看上面这张图,你会发现我们在计算兔子序列的时候,有大量重复的计算,比如算F(10)=F(9)+F(8),F(9)=F(8)+F(7),F(8)需要重复计算两次~~</p> </li>     <li> <p>怎么破,很容易想到我们需要用一个缓存,把这个计算过的数字存在一个表里面,用的时候若这个数字在这个表,就不用再花cpu去运算,直接取就好了。</p> </li>    </ul>    <p>2).先把上面的代码改一下,我们申明一个count变量,每次递归都存起来,然后最后再返回</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/ae3892bafebcf32864389a7fc38840eb.png"></p>    <p>3).接着演变,我们现在构造一个缓冲区cache</p>    <p>我们查表,比如用字典来保存,比如cache[8]=34,我们只需要查一下8是不是在字典里面就可以了,在的话直接取,不在的话再去用算法计算,是不是很爽</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/c640cffc473229b3f0b225e999722089.png"></p>    <p>看运行40项,几乎不费吹灰之力,非常快</p>    <p>2.爬楼梯</p>    <p>比如我有7阶台阶,我们可以用两种爬发,一次一步或者两步,只能进不能退,算算有多少种爬法</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/fcc0b0c3f90cb4a1da063ecd5cd847e7.png"></p>    <p>我们先简单分析一下:</p>    <ul>     <li> <p>若只有一阶台阶,那么不管是一次选择一步还是两步,都只有一种爬法</p> </li>     <li> <p>若只有两阶台阶,选择一步or两步,会有两种爬法</p> </li>     <li> <p>若只有三阶台阶,选择一步然后一步然后一步,或者一步,两步,或者两步,一步,这样有3种爬法</p> </li>     <li> <p>若只有四阶台阶,选择一步,然后剩下3阶台阶的爬法,这3阶爬法可以直接取前面3阶台阶的计算结果</p> </li>    </ul>    <p>我们先写源码,源码很简单用递归搞定,首先设计递归的出口,当只有1阶或者小于1阶台阶时候,直接return 1</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/e80f4b2c8e4a4c6de01d87f7a0f0be94.png"></p>    <p>大家有没有发现这个爬楼梯一样存在重复计算的问题,比如5阶的时候,一步一步然后剩下3步,或者两步然后剩下3步</p>    <p>一样需要用到兔子序列的cache方法,那么在climb函数中再重复写一篇,是不是很累赘,这不是Pythonic的风格,有没有比较好的封装方法呢,同时又能不改动原始的代码呢~~ <strong>有的,牛逼闪闪的Python当然有,就是我们的装饰器啦,</strong> 好我们看装饰器如何封装搞定</p>    <p>3.装饰器封装</p>    <p>对于兔子序列和爬楼梯,我们用装饰器去封装一下,怎么封装呢,我们一步一步来,参考上一篇入门很容易构建出来</p>    <p>1).创建一个装饰器</p>    <p>def decorate(func):</p>    <p>cache={}</p>    <p>def wrap(n):</p>    <p>if n not in cache:</p>    <p>cache[n]=func(n)</p>    <p>return cache[n]</p>    <p>return wrap</p>    <p>2).装饰一下斐波那契数列</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/f90fb39bab2ff02b5579005f545be57a.png"></p>    <p>是不是很简洁,装饰器真是个好东西啊~~</p>    <p>3).装饰器参数升级</p>    <p>大家有没有发现我们上面构造的装饰器,入参是一个参数n.如果碰到需要传入的多个参数的函数怎么办, <strong>比如我们的爬楼梯原函数就是2个参数,</strong> 所以我们需要把装饰器写更通俗一点,对用变参</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/bb35fc29d394fecf6d1b58b76d046321.png"></p>    <p>留几个问题:</p>    <p>1.print climb(5,(1,2))为啥不是[1,2]</p>    <p>2.为啥不能加else</p>    <p>def decorator(func):</p>    <p>cache={}</p>    <p>def wrap(*args):</p>    <p>if args not in cache:</p>    <p>cache[args]=func(*args)</p>    <p>else:</p>    <p>return cache[args]</p>    <p>return wrap</p>    <p>3.加缓冲的时候</p>    <p>def fib(n,cache=None):</p>    <p>为啥不能写成def fib(n,cache={}):</p>    <p>好了 <strong>装饰器的妙用就讲到这里,</strong> 大家想一想如果我们还有类似的代码需要缓存机制,是不是只需要用装饰器封装一下就行了,是不是代码简洁很多而且容易维护和扩展功能,讲到这里 <strong>大家是不是对装饰器的妙用有了进一步的理解</strong> ,若有什么不懂的,也可以留言跟我探讨交流</p>    <p> </p>    <p> </p>    <p>来自:https://zhuanlan.zhihu.com/p/26151166</p>    <p> </p>