为什么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区分开。使用该装饰器时,他会在内部搞一个字典,字典特征还记得么,查找快,以空间换时间。

Last modification:July 9, 2022
如果觉得我的内容对你有用,请随意赞赏