为什么python递归效率低?
简单来讲
1。python是一个巨大的栈机器,进出栈可是非常耗时的(暂且不考虑是否io阻塞等问题)
2。运行递归的时候,单单对于斐波那契来说,相同的值都会重新计算一次(这也是优化的关键)
综上,一般来说,py的递归算法比迭代算法要慢。但是可能递归的语法更简洁
@functools.lru_cache()做“备忘”
原理根据上面的就大都晓得了,减少调用的次数改为直接查询。
这是标准库 functools里面的一个装饰器,要使用它,你得先impor
下面是原代码
def f(n):
if n<2:
return n
return f(n-2)+f(n-1)
优化后....
import functools
@functools.lru_cache()
def f(n):
if n<2:
return n
return f(n-2)+f(n-1)
以第20项为例子,即f(20)
原代码
1.52 ms ± 21.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
优化后
61.7 ns ± 1.08 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
注意!
这性能我估摸还跟你配置有关系。
该备忘装饰器是一个参数化装饰器,你可以百度获取更多,他还可以设置一下备忘的具体多少,还可以把1和1.0区分开。使用该装饰器时,他会在内部搞一个字典,字典特征还记得么,查找快,以空间换时间。