 # Accelerating with memoization

Memoization can be incredible useful for expensive calculations. Just look at the results at the bottom of the post to check how long the 2 functions (with and without memoization) take to run the computation of fib 35.

``````import time

def fib_slow(n):
if n < 2:
return n
else:
n_1 = fib_slow(n - 1)
n_2 = fib_slow(n - 2)
return n_1 + n_2

fib_dict = {}

def fib_fast(n):
global fib_dict
if n < 2:
return n
else:
if (n-1) in fib_dict:
n_1 = fib_dict[n - 1]
else:
n_1 = fib_fast(n - 1)
fib_dict[(n - 1)] = n_1

if (n - 2) in fib_dict:
n_2 = fib_dict[n - 2]
else:
n_2 = fib_fast(n - 2)
fib_dict[(n - 2)] = n_2

return n_1 + n_2
``````

Running…

``````n = 35
print "Calculating fib of " + str(n)
print "Using fib_slow (without memoization)"
start_time = time.time()
print fib_slow(n)
print time.time() - start_time, "seconds"
print "Accelerating... (with memoization)"
start_time = time.time()
print fib_fast(n)
print '{0:.10f}'.format(time.time() - start_time), "seconds"
``````

we get…

Calculating fib of 35
Using fib_slow (without memoization)
9227465
11.9559807777 seconds
Accelerating… (with memoization)
9227465
0.0000698566 seconds