# Cache in python?

1. Jul 21, 2008

### R.Harmon

Hey, I decided to start learning python so I downloaded it yesterday and decided to try and make a simple program to produce the Fibonacci series. I managed to do it using a function similar to that on wikibooks:

def fib(n):
if n < 2:
return n
else:
return fib(n - 1) + fib(n - 2)

However, beneath that is a version with cache, where the code is:

def fib(n):
cache = {0: 0, 1: 1}
def xfib(n):
if n not in cache:
cache[n] = xfib(n-1) + xfib(n-2)
return cache[n]
assert n >= 0
return xfib(n)

I tested both these and found the 2nd is far quicker to produce the series, but I don't really understand why, mainly because I can't seem to work out what the line "cache = {0: 0, 1: 1}" is doing, so I was wondering if anyone knows what this piece of code means, and what its telling the program to do subsequently? Hope that's clear, thanks for any help!

2. Jul 21, 2008

### mgb_phys

It is creating a dictionary which stores the numbers '0' and '1' with the keys '0' and '1'
Dictionaries are an important paqrt of dynamic languages like python - think of them as mini databases, they let you store a value by giving it a key and then very quickly retreive it by just knowing the key. (They are called hashes in other languages)

In this case it just stores the fib sequence as it goes along and uses this cache to quickly calculate the next value by adding the previous two. The cache is a quick way of storing the last two values.

3. Jul 22, 2008

### Mephisto

Thats the initial conditions. Its saying that fib(0) is 0 and fib(1) is 1.

for example
a={1:"hello", 2:"bye"}
for example declares dict indexed by the numbers, so
a[1] returns "hello"
a[2] returns "bye"

4. Jul 22, 2008

### Staff: Mentor

Just count the number of addition operations required to do each.

5. Jul 22, 2008

### R.Harmon

That definitely helps clear things up, thanks alot everyone.