geeknam's blog

A young inspired developer.

Fibonacci With Caching

Here is my attempt to compare the performance of fibonacci with different ways of caching the results. First implementation uses memoization decorator whereas the second one makes use of defaultdict for caching. You can read my previous blog post on caching with defaultdict.

Fibonacci 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import timeit

def memoize(function):
    memo = {}

    def wrapper(*args):
        if args in memo:
            return memo[args]
        else:
            rv = function(*args)
            memo[args] = rv
            return rv

    return wrapper


@memoize
def fib(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return fib(num - 1) + fib(num - 2)


t = timeit.Timer(stmt="fib(150)", setup="from __main__ import fib")
print t.timeit()

# Approximate Result: 0.482068061829 seconds
Fibonacci 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

from collections import defaultdict
import timeit

class FibCache(defaultdict):

    def __init__(self, fn):
        self.fn = fn

    def __missing__(self, num):
        self[num] = self.fn(num, self)
        return self[num]


def fib(num, cache):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return cache[num - 1] + cache[num - 2]


fib_cache = FibCache(fib)

t = timeit.Timer(stmt="fib_cache[150]", setup="from __main__ import fib_cache")
print t.timeit()

# Approximate Result: 0.268569946289 seconds

Note: Default number of loops for timeit is 1000000

If you’re looking to hire a Python programmer, this would be a great programming question. Challenge all the candidates to write the fastest fibonacci function. Hire the one whose code is the fastest.

Feel free to suggest better/faster implementations if you know any, I’d be glad to add more to the collection.

Comments