Understanding Caching in Python Fibonacci Series

[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!

 

[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.

 

[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"

 

[Dale]

I tested both these and found the 2nd is far quicker to produce the series, but I don't really understand why

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

 

[R.Harmon]

That definitely helps clear things up, thanks a lot everyone.