Fibonacci sequence/number dynamic programming

Question

I'm trying to improve my programming logic skills and I was watching one of the videos on how to approach Fibonacci numbers.

After looking at the pseudo code at 6:34 I wrote this:

In [14]: 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

Which works great however when I watched the video to the end when the guy reviled his python code, I discovered that it was slightly different to mine.

CS Dojo code:

In [68]: def fib_dyn_2(x, memo):     
    ...:     if memo[x] is not None:
    ...:         return memo[x]
    ...:     if x == 1 or x == 2:
    ...:         result = 1
    ...:     else:
    ...:         result = fib_dyn_2(x-1, memo) + fib_dyn_2(x-2, memo)
    ...:     memo[x] = result
    ...:     return result
    ...: 
    ...: def fib_memo(x):
    ...:     memo = [None] * (x + 1)
    ...:     return fib_dyn_2(x, memo)

There is "slight" difference I use dictionary for caching he uses list.

What got me is that my code appears to be a little bit faster. When getting to numbers in the sequence X >= 100 and as well when running the same number is the sequence more than once.

i.e. My code:

In [4]: %time my_fib(100)
CPU times: user 70 µs, sys: 44 µs, total: 114 µs
Wall time: 92 µs
Out[4]: 354224848179261915075L

CS Dojo code:

In [5]: %time fib_memo(100)
CPU times: user 99 µs, sys: 128 µs, total: 227 µs
Wall time: 187 µs
Out[5]: 354224848179261915075L

Question is which one is "better" or more desired as an answer?

I think you can't really answer that question. It depends. Usually you only do such performance optimizations, if you really need to, because they make the code a bit more complex (even if it is only a small bit in your example), which often reduces the readability and maintanability of the code, because the main logic might "drown" in technical code — jottbe, Jun 15 '19 at 10:15
So this kind of caching is generally a good idea, if performance is a real issue, but probably the creator of the video skipped this step to just introduce the concept of funcional programming and real functional programming languages do such a kind of cashing themselfes (I think haskell does this for example). — jottbe, Jun 15 '19 at 10:17
@jottbe I assume that you would prefer `CS Dojo` version based on readability, am I correct ? — MMT, Jun 15 '19 at 10:18
Ah ok, sorry I was mislead. I thought this is about functional programming, but it seems the video adresses performance. Hmm strange, that your solution is faster, because hashed lookups like in a dict are usually slower than index based lookups. How did you initialize memo btw? So if performance is not issue, I neither would use the original version create by CS Dojo. — jottbe, Jun 15 '19 at 10:32
I think the reason that your code is so much faster is because when you define `my_fib` the `dict()` is created then and there and is already present for every time you run the function. `fib_memo` on the other hand creates a new list every time you call the function. If you only timed `fib_dyn_2` instead the times would probably be far closer. Hope this helps. TLDR: Dictionaries you define in the parameter list are created as soon as the function is defined. — dangee1705, Jun 15 '19 at 10:42
The reason your function is faster the second time is because the way it is written subsequent calls reuse the values calculated and cahced the first time — it doesn't really have anything to do with using a `dict` per se. — martineau, Jun 15 '19 at 11:04

score 1 · Answer 1 · answered Jun 15 '19 at 11:05

1

While memoized version of Fibonacci numbers calculation is much better than naive, recursive approach, I encourage you to check the solution based on Matrix Form of Fibonacci numbers:

https://stackoverflow.com/a/23462371/1570854

answered Jun 15 '19 at 11:05

Lesiak

22,088
2
41
65

Alain T. · Answer 2 · 2019-06-16T13:59:53.343

Intuitively, list based memoization should be marginally faster than dictionary based. I found that the algorithm and order of calls has a large impact on the result so a fair comparison requires some care (e.g. using preallocation vs appending)

I made a few comparison tests that seem to confirm this. You can also get significant performance variations with the kind of operation / logic you use in the algorithm.

Here are the test results (for 100 repetitions of getting the 900th fibonacci number):

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)

Here are the function implementations:

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]

EDIT Added an exponential algorithm that responds in O(log(N)) time

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

And the test procedure

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)

BTW I assume that your objective is to explore dynamic programming. Otherwise using double recursion for a fibonacci function is certainly the worst possible approach.

score 0 · Answer 3 · answered Jun 15 '19 at 11:02

I just tried to verify if there is a notable performance difference between the dict and the list version. It looks like there is only a very tiny difference between the two methods. Btw. note that I also measured the creation of the cache-list. If I compare the times the "unix" time command prints, I recognize no difference at all, but of course this also measures the time the os needs to load the python interpreter and thus is not so reliable.

from datetime import datetime
def fib_cached(n, cache=None):
    if n <= 2:
        return 1
    if cache[n] is None:
        fib_n= fib_cached(n-1, cache) + fib_cached(n-2, cache)
        cache[n]= fib_n
    else:
        fib_n= cache[n]
    return fib_n


n= 950

before= datetime.now()
print(fib_cached(n, cache=[None]*(n+1)))
print(datetime.now() - before)

score 0 · Answer 4 · answered Jun 16 '19 at 06:07

Experimenting a bit, I found a variation of your code that beats all the other candidates in the timings of @AlainT., even the iterative one. There are two places performance is lost. First, this logic:

if memo.get(x):

is slower than the simpler:

if x in memo:

Since on a hit you end up looking up the value twice, instead of once in the next line. However, a more substantial improvement comes here:

result = my_fib(x - 1, memo) + my_fib(x - 2, memo)

You've already defaulted the memo argument, why are you passing it? You can significant speed up, in the timings, by doing:

result = my_fib(x - 1) + my_fib(x - 2)

My reworked function:

def my_fib(x, memo={1:1, 2:1}):
     if x in memo:
         return memo[x]

     memo[x] = result = my_fib(x - 1) + my_fib(x - 2)

     return result

Fibonacci sequence/number dynamic programming

4 Answers4