Explain how to use memory caches in Python

Question

I have the following recursive solution for the nth fibonacci number:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

x=input('which fibonnaci do you want?')
print fib(x)

I need to change this, so that it uses a stored memory cache and gets stuff out of that to speed up the process. I really don't know how to do this and google isn't helping.

Answer 1

decorate your function with this:

http://docs.python.org/3/library/functools.html#functools.lru_cache

one of the examples in the docs is, in fact, fibonacci:

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

Which gives:

>>> [fib(n) for n in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

>>> fib.cache_info()
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)

UPDATE

This only works in Python3.2+

For a backport, checkout this page: http://code.activestate.com/recipes/578078-py26-and-py30-backport-of-python-33s-lru-cache/