您当前的位置:首页 > 计算机 > 编程开发 > Python

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

时间:09-09来源:作者:点击数:

我们围绕一个数学问题来说明本文的思想,组合数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呢?这算是修饰器的小坑吧,目前还没有找到解决办法(谁要是知道的话一定要告诉我,谢谢),所以推荐使用修饰器的用法,不建议把修饰器当函数来使用。

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

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门