Интуитивно понятно, что запоминание на основе списка должно быть немного быстрее, чем на основе словаря.Я обнаружил, что алгоритм и порядок вызовов оказывают большое влияние на результат, поэтому для правильного сравнения требуется некоторая осторожность (например, использование предварительного распределения против добавления)
Я провел несколько сравнительных тестов, которые, кажется, подтверждают это.Вы также можете получить значительные изменения производительности с типом операции / логики, которую вы используете в алгоритме.
Вот результаты теста (для 100 повторений получения 900-го числа Фибоначчи):
my_fib(N) 0.0578 Original
fibo(N) 0.0089 Iterative algorithm
simpleFibo(N) 0.0248 Single recursion algorithm
dynaFibo(N) 0.0463 Double recursion with dictionary based memoization
dynaFibo2(N) 0.0440 Double recursion with list based memoization
binFibo(N) 0.0012 Iterative exponential algorithm
(this one responds in O(log(N)) time)
Вот реализации функции:
def my_fib(x, memo=dict()):
if memo.get(x):
return memo[x]
if x == 1 or x == 2:
result = 1
else:
result = my_fib(x - 1, memo) + my_fib(x -2, memo)
memo[x] = result
return result
def fibo(N):
a = b = 1
for _ in range(2,N): a,b = b,a+b
return b
def simpleFibo(N,a=0,b=1):
if N < 3: return a+b
return simpleFibo(N-1,b,a+b)
def dynaFibo(N,memo={1:1,2:1}):
if N not in memo:
memo[N] = dynaFibo(N-1,memo) + dynaFibo(N-2,memo)
return memo[N]
def dynaFibo2(N,memo=None):
if not memo: memo = [0,1,1]+[0]*N
if not memo[N]: memo[N] = dynaFibo2(N-1,memo) + dynaFibo2(N-2,memo)
return memo[N]
РЕДАКТИРОВАТЬ Добавлен экспоненциальный алгоритм, который отвечает за O (log (N)) времени
def binFibo(N):
a,b = 0,1
f0,f1 = 1,1
r,s = (1,1) if N&1 else (0,1)
N //=2
while N > 0:
a,b = f0*a+f1*b, f0*b+f1*(a+b)
f0,f1 = b-a,a
if N&1: r,s = f0*r+f1*s, f0*s+f1*(r+s)
N //= 2
return r
И процедура теста
from timeit import timeit
count = 100
N = 990
t= timeit(lambda:my_fib(N,dict()), number=count) # providing dict() to avoid reuse between repetitions
print("my_fib(N)",t)
t= timeit(lambda:fibo(N), number=count)
print("fibo(N)",t)
t= timeit(lambda:simpleFibo(N), number=count)
print("simpleFibo(N)",t)
t= timeit(lambda:dynaFibo(N,{1:1,2:1}), number=count) # providing dict() to avoid reuse between repetitions
print("dynaFibo(N)",t)
t= timeit(lambda:dynaFibo2(N), number=count)
print("dynaFibo2(N)",t)
t= timeit(lambda:binFibo(N), number=count)
print("binFibo(N)",t)
Кстати, я предполагаю, что ваша цельэто изучить динамическое программирование.В противном случае использование двойной рекурсии для функции Фибоначчи, безусловно, является худшим из возможных подходов.