Did you get the memo?

In [1]:

def fib(n):
    """Return Nth Number of Fibonacci Sequence."""
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

In [2]:

%%timeit -n 1000
fib(20)

1000 loops, best of 3: 2.59 ms per loop

• Too slow ...
• Can we go faster?
• What are we calulating?
• What if we only calulated once?
• What built in data structure can we use?

In [4]:

def fibonacci(n):
    """Return nth number of fibonacci sequence"""
    if n <= 0:
        return 0
    l = [0, 1]
    while len(l) < n:
        l.append(l[-1] + l[-2])
    return l[n-1]

In [5]:

%%timeit -n 1000
fibonacci(20)

1000 loops, best of 3: 4.7 µs per loop

In [9]:

memo = {}
def fib_memoized(n):
  '''calculate the fibonacci number for int n and return int '''
  if n in memo:
    return memo[n]
  if n == 1:
    f = 0
  elif n == 2:
    f = 1
  else:
    f = fib_memoized(n - 1) + fib_memoized(n - 2)
  memo[n] = f
  return f

How slow is it now?

In [10]:

%%timeit -n 1000
fib_memoized(20)

1000 loops, best of 3: 176 ns per loop

There is a faster algorithm –look up Knuth And other ways to do this in Python: Warning: code from the net –do not copy and paste

In [ ]: