Below are two ways to calculate an element of the Fibonacci series. Can someone please help me understand why fib1
is so much faster (over 60x) than fib2
?
fib2
is just an assignment and a decrement whereas fib1
involves a dictionary and recursive calls.
Thanks.
import timeit
def fib1(n, lookup=dict()):
if n == 0 or n == 1:
lookup[n] = n
elif n not in lookup:
lookup[n] = fib1(n - 1, lookup) + fib1(n - 2, lookup)
return lookup[n]
def fib2(n):
n1, n2 = 0, 1
while n > 1:
n -= 1
n1, n2 = n2, n1 + n2
return n2
n = 1000
recursive = timeit.timeit(lambda: fib1(984), number=n)
iterative = timeit.timeit(lambda: fib2(984), number=n)
print("recursive:", recursive)
print("iterative:", iterative)
"""
output:
recursive: 0.0012962640030309558
iterative: 0.08570116000191774
"""
fib1
shares its cache between the 1000 calls fromtimeit
;fib2
doesn't get to reuse anything between its 1000 calls. But "Help me understand my own code" isn't really "code review". \$\endgroup\$ – Peter Taylor Oct 31 '19 at 8:33lookup
dictionary is acting as a mutable default argument. \$\endgroup\$ – JAD Oct 31 '19 at 8:49print(n)
statement at the start of fib1. \$\endgroup\$ – Josiah Oct 31 '19 at 9:40