针对递归函数的优化与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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信宝典

Python学习教程(二)

输入输出 交互式输入输出 在很多时候,你会想要让你的程序与用户(可能是你自己)交互。你会从用户那里得到输入,然后打印一些结果。我们可以分别使用raw_input...

2758
来自专栏人工智能头条

TensorFlow架构与设计:变量初始化

1004
来自专栏程序员互动联盟

【答疑释惑】C语言里面结构体大小统计方法

之前说过一个关于结构体在内存中所占字节数的问题,我们知道结构体长度的计算并不是所有成员长度的相加,而是因为编译器优化会对其进行对齐,这样会优化访问速度等。 那...

3167
来自专栏吴伟祥

关于“分类”的应用 原

三、SQL中区分类别的过滤条件:比如取分类2,那么就是 2=2 <![CDATA[ & ]]>type

842
来自专栏debugeeker的专栏

《coredump问题原理探究》Linux x86版5.7节C风格数据结构内存布局之结构体数组

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

771
来自专栏数据结构与算法

07:机器翻译

7:机器翻译 总时间限制: 1000ms 内存限制: 65536kB描述 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 这个翻译软件...

4076
来自专栏Laoqi's Linux运维专列

python3–内置模块Ⅱ

4888
来自专栏机器学习算法与Python学习

Python:numpy总结(4)

31、chr函数,获取指定的字符 例子: #获取指定的字符for i in range(65,70): print str(chr(i))...

3959
来自专栏大闲人柴毛毛

Redis源码分析(三)——Redis数据结构-字典

1. 数据结构 ? 1.1 哈希表 typedef struct dictht{ dictEntry **table; unsigned long s...

3035
来自专栏闻道于事

Java异常处理中的恢复模型

2774

扫码关注云+社区

领取腾讯云代金券