Сравните скорость алгоритма Фибоначчи - PullRequest
Новая
       11

Сравните скорость алгоритма Фибоначчи

0 голосов
/ 10 июня 2018

Я попробовал два алгоритма для ряда Фибоначчи и сравнил скорость.

Первый - по степеням матриц через 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 первый должен быть быстрее.

Я сравниваю их скорость следующим образом: 

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

Правильно ли я сравниваю их скорость?Если да, может кто-нибудь объяснить, почему второй быстрее?Спасибо.

1 Ответ

0 голосов
/ 10 июня 2018

Используйте 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 работает быстрее.

...