0
\$\begingroup\$

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
"""
Improve this question
\$\endgroup\$
5
  • 7
    \$\begingroup\$ fib1 shares its cache between the 1000 calls from timeit; 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:33
  • 1
    \$\begingroup\$ To complement Peter's answer, see this article. Your lookup dictionary is acting as a mutable default argument. \$\endgroup\$ – JAD Oct 31 '19 at 8:49
  • \$\begingroup\$ If I were being truly pedantic the correct thing to do would have been to just post the last sentence of my earlier comment, so as not to encourage off-topic questions. \$\endgroup\$ – Peter Taylor Oct 31 '19 at 8:51
  • \$\begingroup\$ I made a similar sort of mistake at work recently. We're always taught to profile a bunch of times to take an average, but that can mask if one run (say, the first run) is massively slower than the rest because a bunch of work from the first run is being cached. Peter and JAD explain why, that's happening. If you change n to 1, you'll see the actual runtime performance is what you'd expect: the loop is much faster. As to which measurement you care about, it depends on your use case. If your code needs to calculate fib once, use fib2. If it needes to call it repeatedly, perhaps use fib1. \$\endgroup\$ – Josiah Oct 31 '19 at 9:38
  • \$\begingroup\$ It may be informative to put a print(n) statement at the start of fib1. \$\endgroup\$ – Josiah Oct 31 '19 at 9:40
1
\$\begingroup\$

The key difference is in a technic called "memoization". According to Wikipedia: In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. So basically, in the first function, you save all the previous results while on the second function you need to calculate everything again from the beginning for every new call. A quick search on the internet gives this tutorial if you wish to learn more.

Improve this answer
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.