Python Projects for Beginners a ten-Week Bootcamp Approach to Python Programming

Understanding Memoization

When you go to a web page for the first time, your browser takes a little while to load the images and files required by the page. The second time you go to the exact same page, it usually loads much faster. This is because your browser is using a technique known as “caching.” When you loaded the page the first time, it saved the images and files locally. The second time you accessed the web page, instead of re-downloading all the images and files, it simply loaded them from the cache. This improves our experiences on the Web.
In computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of previously called functions and returning the saved result when trying to calculate the same sequence. This is simply known as “caching,” and the preceding paragraph is a real-life example of how memoization can improve performance. Let’s look at some examples of how memoization can improve our recursive functions.

Using Memoization

In order to apply memoization to the Fibonacci sequence, we must understand what the best method of caching values would be. In Python, dictionaries give us the ability to store values based on a given key. They are also based on constant time in terms of Big O Notation. We’ll get to this topic in the next week. For now, just understand that dictionaries are much faster at returning information than most other data collections. Due to the speed and unique key structure of dictionaries, we can use them to store the value of each Fibonacci sequence. This way, once a single sequence like fib(3) has been calculated, it does not need to be calculated again. It is simply stored into the cache and retrieved when needed. Let’s try it out:

1| # using memoization with the fibonacci sequence
3| cache = { } # used to cache values to be used later 5| def fib(n):
6| if n in cache:
7| return cache[ n ] # return value stored in dictionary
9| result = 0
11| # base case 12| if n < = 1:
13| result = n 14| else:
15| result = fib( n – 1 ) + fib( n -2 )
17| cache[ n ] = result # save result into dictionary with n as the key
19| return result
21| print( fib(50) ) # calculates almost instantly

Go ahead and run the cell. Notice this time it was able to calculate fib(50) almost instantly. If we ran this without caching values, it could have taken hours or days to execute the same calculation. This is the beauty of memoization at work. The process begins by passing the argument into fib. The program then checks to see if the argument appears as a key within the cache. If it does, it simply returns the value. If not, however, it needs to calculate the proper result by using recursion until the base case is reached.
Once the base is reached, the values begin to save as key-value pairs within the cache.
As the recursive calls begin to work their way back up the structure, they simply pull the values from the dictionary. Rather than having to calculate fib(2) thousands of times, it only calculated it once thanks to memoization.
Note Memoization is not perfect; there is a limit to how much you can store in a single cache.