我们围绕一个数学问题来说明本文的思想,组合数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呢?这算是修饰器的小坑吧,目前还没有找到解决办法(谁要是知道的话一定要告诉我,谢谢),所以推荐使用修饰器的用法,不建议把修饰器当函数来使用。
最后需要说明的是,本文的思想只是缓解了问题,并不会彻底解决函数递归调用对递归深度的限制,随着参数的增大,一样会崩溃。