Need an explanation on why this line makes everything faster in my Fibonacci calculator. (Python)

Question

Could anyone explain why this line fibValue[n] = result makes everything so much faster? Just taking out that line it takes ages for anything over 30 to load. Thanks in advance!

fibValue = { 0: 0, 1: 1}

def fib(n):
    if n in fibValue.keys():
        return fibValue[n]
    else:
        result = fib(n-1) + fib(n-2)
        fibValue[n] = result
        return result

result = fib(int(input("Enter number: ")))
print(result)

You are _caching_ earlier results. You trade memory against run-time , often made choice ... btw. you store too much , you only need 2 numbers to store for your little program — Patrick Artner, Dec 19 '18 at 13:50
I got no clue what that line does,I tried taking it out while practicing, cause I thought it wasnt doing much but it just made everything slower. — Flapjack, Dec 19 '18 at 13:51
You will find the explanation here https://www.youtube.com/watch?v=vJ2fu-pnFTw — guttume, Dec 19 '18 at 13:51
See [fiboinaci generator](https://stackoverflow.com/a/24846766/7505395) answer for even faster one - it only stores 2 numbers and does not need the overhead of a dictionary — Patrick Artner, Dec 19 '18 at 13:54
Note that the `if n in fibValue.keys():` test is quite inefficient (it builds a sequence of keys and do a sequential lookup - which is 0(n)) - you should use `if n in fibValues:` instead (which uses the hash of n to do a 0(1) lookup). — bruno desthuilliers, Dec 19 '18 at 14:11

TrebledJ · Accepted Answer · 2019-03-04T14:39:50.687

That right there is a technique called dynamic programming (aka. memoisation), whereby you store and reuse computed results. This makes lookup and computation much, much faster later on.

When you remove fibValue[n] = result, you don't store the result, and by not storing the result, you need to recompute the fibonacci for that particular number n.

Consider computing fib(6). On the first function call, you get

fib(6) = fib(5) + fib(4)

By recursion, this gives

fib(6) =                       fib(4)               +            fib(3)        +             fib(3)       +     fib(2)

fib(6) =            fib(3)        +     fib(2)      +     fib(2)      + fib(1) +      fib(2)     + fib(1) + fib(1) + fib(0)

fib(6) =      fib(2)     + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

fib(6) = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(1) + fib(0)

fib(6) =    1   +    1   +    1   +    1   +    1   +    1   +    1   +    1   +   1   +    1   +    1   +    1   +    1

fib(6) =    13

You could see that fib(3) and fib(2) were computed at least 3 times each. Now consider if your input is much bigger (say 1000). You'd be computing fib(3), fib(100), fib(200), etc. repeatedly. This wastes a huge amount of time. Thus, to save time (since we're programmers, we're very woo about time), we trade in space (i.e. memory) to cache previous computations and thus... save time by doing lookup on the cache.

The time complexity of performing lookup on a Python dictionary is (on average) O(1), this takes constant time, and is the best thing a programmer might wish for in an algorithm. Compare that to the unwieldy time complexity of computing a fib(n) from scratch. (Note that, as @brunodesthuilliers commented, your function currently performs lookup by iterating through a dict.keys() object, which will result in a (worse-case) O(n) time-complexity for lookup. Simply changing if n in fibValue.keys() to if n in fibValue may result in faster computation.)

As suggested by @PatrickArtner, if you're only finding a single fibonacci value, you could make your fibonacci calculator more efficient time-and-space-wise by only storing two values (i.e. the most recent fib values) instead of caching every result.

But its badly done - you only need to store 2 numbers ... not a dict of all of them. — Patrick Artner, Dec 19 '18 at 13:51
Well, that'd be fine if you're calculating a single value. But if you're making multiple queries? — TrebledJ, Dec 19 '18 at 13:52
The program does not - if you did, it might be warranted to keep them around for some time — Patrick Artner, Dec 19 '18 at 13:53
@PatrickArtner Ty a lot both of you,It did help a lot. I will check out what you linked,Patrick. — Flapjack, Dec 19 '18 at 14:00
"The time complexity of performing lookup on a Python dictionary is (on average) O(1)," => when it's properly done (`if key in dict:`) - not when key is looked up on `dict.keys()` (as in the OP snippet), which is 0(n) — bruno desthuilliers, Dec 19 '18 at 14:13
@brunodesthuilliers Ah that'd become lookup in a list-like thingy wouldn't it. Will edit my answer. — TrebledJ, Dec 19 '18 at 14:14

score 0 · Answer 2 · answered Dec 19 '18 at 13:57

The technique that you used here to compute fibonacci series is called Dynamic Programming method.

Dynamic Programming method divides the problems into the sub problems and solves each sub problem and saves the result of each sub problem.

These results are used to solve other sub problems. So it makes the algorithm faster.

Need an explanation on why this line makes everything faster in my Fibonacci calculator. (Python)

2 Answers2