Loading... ## 为什么python递归效率低? 简单来讲 1。python是一个巨大的栈机器,进出栈可是非常耗时的(暂且不考虑是否io阻塞等问题) 2。运行递归的时候,单单对于斐波那契来说,相同的值都会重新计算一次(这也是优化的关键) 综上,一般来说,py的递归算法比迭代算法要慢。但是可能递归的语法更简洁 ## @functools.lru_cache()做“备忘” 原理根据上面的就大都晓得了,减少调用的次数改为直接查询。 这是标准库 functools里面的一个装饰器,要使用它,你得先impor **下面是原代码** ```python def f(n): if n<2: return n return f(n-2)+f(n-1) ``` **优化后....** ```python 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 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 1 如果觉得我的内容对你有用,请随意赞赏