python - 比较斐波那契算法的速度

Question

我尝试了两种斐波那契数列算法并比较了速度。

第一个是通过 Numpy 的矩阵的幂(我也写了自己的函数，但似乎 numpy 更快)。

import numpy as np
import time

def fibonacci_power(n):
    F=np.matrix('1,1;1,0')
    Fn=F**(n-1)
    return Fn[0,0]

第二种是缩短内存的动态规划。

def fibonacci_mem(n):
    f=[0, 1]
    if n<=1:
        return f[n]
    for i in range(2, n+1):
        temp=f[1]
        f[1]=f[1]+f[0]
        f[0]=temp
    return f[1]

第一个的时间复杂度是O(log n)，第二个是O(n)。所以对于更大的 n，第一个应该更快。

我比较他们的速度如下:

def main():
    n=90

    start=time.time()
    f1=fibonacci_power(n)
    f1_time=time.time()-start
    print('Power/Numpy result: '+str(f1)+' time: '+str(f1_time))

    start=time.time()
    f3=fibonacci_mem(n)
    f3_time=time.time()-start
    print('Memory result: '+str(f3)+' time: '+str(f3_time))

结果是:

Power/Numpy result: 2880067194370816120 time: 0.00021696090698242188
Memory result: 2880067194370816120 time: 4.410743713378906e-05

我是否以正确的方式比较了它们的速度？如果是，谁能解释为什么第二个更快？谢谢。

Answer 1

使用 cProfile，它会显示您的函数正在执行的所有操作(调用等)。并且，比较一下:

import cProfile
cProfile.run('fibonacci_power(150)')
#compare it to
cProfile.run('fibonacci_mem(150)')

对此:

import cProfile
cProfile.run('fibonacci_power(15000)')
#compare it to
cProfile.run('fibonacci_mem(15000)')

如您所见，NumPy 使用这么多东西来完成任务，因为矩阵方法更复杂。您的代码更简单，它只使用了一些内置的东西。 NumPy 用于做更复杂的事情，如果'n'是小数字，它会比你写的小函数慢。看看cProfile的解释，就更清楚了。当然，对于大数和长期运行，NumPy 更快。