SolarPixelGaming SolarPixelGaming - 1 month ago 7
Python Question

Python - Modify dictionary from function

Okay, this question is a little strange, but I was wondering if I could do it like this.

I'm working on a simple Fibonacci number generator for fun since I was interested in programming it.
So I wrote this out:

def f(n):
if n == 1: return 1
if n == 2: return 2
else:
return f(n-1) + f(n-2)


and that ran very slowly, taking 15 seconds to do
f(30)
on my computer.
So then I wrote this:

def f(n):
global a
if n == 1: return 1
if n == 2: return 1
else:
if "fib(%s)" % n in a:
return a["fib(%s)" % n]
else:
z = f(n-1) + f(n-2)
a["fib(%s)" % n] = z
return z


which basically stores previous results in a dictionary like so:

{'f(1)':1,'f(2)':2,'f(3)':3,'f(4)':5}
and so on. In the function it would check if that result was in that dictionary, then just use that instead of having to redo all the calculations.

This made it tons faster. I could do
f(100)
and it instantly appear. Going by intervals of 500, I got to
f(4000)
and it was still instantaneous. The one problem was that the dictionary was getting stupidly big.

So I added
a = {}
to the end of the function, and that didn't work; it still left
a
as a massive dict.

So doing this:

def f(n):
global a
if n == 1: return 1
if n == 2: return 1
else:
if "fib(%s)" % n in a:
return a["fib(%s)" % n]
else:
z = f(n-1) + f(n-2)
a["fib(%s)" % n] = z
return z
a = {}


didn't work. but if I do this:

def f(n):
global a
if n == 1: return 1
if n == 2: return 1
else:
if "fib(%s)" % n in a:
return a["fib(%s)" % n]
else:
z = f(n-1) + f(n-2)
a["fib(%s)" % n] = z
return z
# now run the function
f(100)
a = {}


a
gets reset to an empty dictionary. Why does this happen and how can I fix it?

Answer

Your a = {} statement inside the function was never being executed; every possible path of execution reaches a return before then. If it WAS executed, you wouldn't have liked the results - it would have executed in every single recursive call to the function, meaning that your dictionary would never hold more than one item! You would somehow have to detect the outermost call and only clear the dict there, or (much simpler) clear it outside of the recursion as in your second example.

Note that much of the size of your dictionary is coming from the strange decision to use a long string key. Keying it with the number itself (as in a[n] = z) would make it much more compact.

(For future reference: the technique you've come up with here, of saving the results from previous function calls, is known as "memoization".)