专栏首页Python小屋针对递归函数的优化与Python修饰器实现

针对递归函数的优化与Python修饰器实现

我们围绕一个数学问题来说明本文的思想,组合数C(n,i),也就是从n个元素中任选i个,共有多少种选法。当然,这个问题有很多种求解方法,例如【最快的组合数算法之Python实现】。本文主要分析组合数的递归求解方法,也就是著名的帕斯卡公式C(n,i) = C(n-1, i) + C(n-1, i-1),首先编写出可以运行的正确代码,然后再进行优化和改进。

import time

from functools import wraps

def f0(n, i):

'''原始版本,随着参数的增大很快就会崩溃'''

if n==i or i==0:

return 1

return f0(n-1, i) + f0(n-1, i-1)

#使用全局的字典来存储中间计算结果,避免重复计算

#并且崩溃会晚一点到来

cache1 = dict()

def f1(n,i):

if n==i or i==0:

return 1

#如果当前参数还没计算过才计算

#如果已经计算过了,就直接返回之前计算的结果

elif (n,i) not in cache1:

cache1[(n,i)] = f(n-1, i) + f(n-1,i-1)

return cache1[(n,i)]

#使用嵌套定义函数来实现同一个问题

def f2(n,i):

cache2 = dict()

def f(n,i):

if n==i or i==0:

return 1

elif (n,i) not in cache2:

cache2[(n,i)] = f(n-1, i) + f(n-1, i-1)

return cache2[(n,i)]

return f(n,i)

#定义修饰器

def cachedFunc(func):

#使用字典存储中间结果

cache = dict()

#对目标函数进行改写

@wraps(func)

def newFunc(*args):

if args not in cache:

cache[args] = func(*args)

return cache[args]

#返回修改过的新函数

return newFunc

#使用修饰器

@cachedFunc

def f3(n, i):

#使用最原始的思路编写代码即可

if n==i or i==0:

return 1

return f3(n-1, i) + f3(n-1, i-1)

#测试不同实现的运行时间

for f in (f0, f1, f2, f3):

start = time.time()

for i in range(100000):

f(15,3)

print(f.__name__, ':', time.time()-start)

运行结果为:

f0 : 19.13409447669983

f1 : 0.04300236701965332

f2 : 4.019229888916016

f3 : 0.03200173377990723

虽然运行效果显示使用修饰器的效果不错,但是大家肯定会有个疑问,是不是针对每个函数都要写一个不同的修饰器呢?实际上是不用的,一般来说,同一个修饰器函数适用于特定的一类问题,是可以重复使用的,例如下面的斐波那契数列问题就重复使用了上面定义的修饰器。

def fib1(i):

if i<2:

return 1

return fib1(i-1) + fib1(i-2)

fib2 = cachedFunc(fib1)

for f in (fib2, fib1):

start = time.time()

for i in range(1000):

f(30)

print(f.__name__, ':', time.time()-start)

运行结果为:

fib1 : 0.4820277690887451

fib1 : 426.09937143325806

太神奇了,居然相差这么多。不过好像有个问题,为啥最后这段代码两次输出的函数名都是fib1呢,第一个为啥不是2呢?这算是修饰器的小坑吧,目前还没有找到解决办法(谁要是知道的话一定要告诉我,谢谢),所以推荐使用修饰器的用法,不建议把修饰器当函数来使用。

最后需要说明的是,本文的思想只是缓解了问题,并不会彻底解决函数递归调用对递归深度的限制,随着参数的增大,一样会崩溃。

本文分享自微信公众号 - Python小屋(Python_xiaowu),作者:董付国

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python数据分析库pandas高级接口dt和str的使用

    Series对象和DataFrame的列数据提供了cat、dt、str三种属性接口(accessors),分别对应分类数据、日期时间数据和字符串数据,通过这几个...

    Python小屋屋主
  • 最优的素数判断代码(Python)是这样写出来的

    素数判断是个很经典的问题,各种语言的程序设计课程都会涉及到,按照素数定义(除了1和自身,素数没有其他因数)很容易写出下面的代码: def isPrime1(n...

    Python小屋屋主
  • Python演示正多边形逼近圆周过程中计算圆周率近似值

    很久以前推送过这样一篇文章,Python使用matplotlib绘制正多边形逼近圆周

    Python小屋屋主
  • 实体类的枚举属性--原来支持枚举类型这么简单,没有EF5.0也可以

        通常,我们都是在业务层和界面层使用枚举类型,这能够为我们编程带来便利,但在数据访问层,不使用枚举类型,因为很多数据库都不支持,比如我们现在用的SqlSe...

    用户1177503
  • 每日一题(3)

    KEN DO EVERTHING
  • USB Storage启动EBox4300

    参考《eBox-4300 Windows Embedded CE 6.0 R2 JumpStart rev 3.5》中,EBox4300可以通过以下途径启动: ...

    ShiJiong
  • 可信计算和可信赖计算的渊源

    看到业界在谈论可信计算时,将任何微软做的事情都称为可信计算,其实这里面发展过程很复杂,历史的交叉结合翻译的错误颇有故事,微软做的一些事情和可信计算既有区...

    Ramos
  • 架构图、用例图、流程图、时序图、类图

    用例图:用例图是指由参与者(Actor)、用例(Use Case),边界以及它们之间的关系构成的用于描述系统功能的视图。是系统的蓝图。

    看、未来
  • 搜狗汪仔《一站到底》完胜人类 背后核心技术曝光

    用户1737318
  • 移动设备上的多位数字识别

    将纸质文档转换为数字文档有着巨大的需求,因为数字文档更容易检索。经过多年的探索和研究,OCR(Optical Character Recognition,光学字...

    云水木石

扫码关注云+社区

领取腾讯云代金券