我正在比较 Python 3 中斐波那契例程的两个版本:
import functools
@functools.lru_cache()
def fibonacci_rec(target: int) -> int:
if target < 2:
return target
res = fibonacci_rec(target - 1) + fibonacci_rec(target - 2)
return res
def fibonacci_it(target: int) -> int:
if target < 2:
return target
n_1 = 2
n_2 = 1
for n in range(3, target):
new = n_2 + n_1
n_2 = n_1
n_1 = new
return n_1
第一个版本是递归的,带有内存(感谢 lru_cache
)。第二种是简单的迭代。
然后我对这两个版本进行了基准测试,我对结果感到有些惊讶:
In [5]: %timeit fibonacci_rec(1000)
82.7 ns ± 2.94 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
In [6]: %timeit fibonacci_it(1000)
67.5 µs ± 2.1 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
迭代版本比递归版本慢很多。当然第一次运行递归版本会花很多时间(缓存所有结果),递归版本占用更多内存空间(存储所有调用)。但我没想到在运行时会有这样的差异。与仅遍历数字和交换变量相比,调用函数不会产生一些开销吗?
最佳答案
如您所见,timeit
多次调用该函数,以获得可靠的测量结果。递归版本的 LRU 缓存不会在调用之间被清除,因此在第一次运行后,fibonacci_rec(1000)
只是立即从缓存中返回,而不进行任何计算。
关于python - 为什么 Fibonacci 迭代比递归版本(带内存)慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63656099/