Memoization in Python

In this tutorial I’m going to introduce you to memoization — a specific type of caching that is used as a software optimization technique. Caching is storing the results of an operation for later use. An example is the storing of browsing history in web browsers so that when an already visited site is visited again it loads faster, but when I talk about memoization in python, it is the caching of function output based on its input or parameters. Once you memoize a function, it will only compute its output once for each set of parameters you call it with, every call after the first, is quickly retrieved from a cache. In this tutorial, you’ll see how and when to use memoize with Python, so you can use it to optimize your own programs and make them run much faster in some cases.

Ideally, you will want to memoize functions that have a deterministic output for a specific input parameter(s) and more importantly expensive function (those that takes long and or much memory to compute). Example of a deterministic function will be the sqrt function to calculate the square root of input because it is sure to produce the same output no matter what. So sqrt(16) will always be 4, In this case, it makes sense to memoize this function given this input rather than re-computing the function with same parameter(s) over and over again. But an example of an expensive and deterministic function will be those implementing recursions, like Fibonacci, Factorial etc. These are where Memoization is needed to speed up part of these parts of the programs that slow it down and take away resources from your machine.

2. Every time the function is called, do one of the following: Return the cached result, if any; or Call the function to compute the missing result, and then update the cache before returning the result to the caller

So there is a data structure to store all results. In our case, we will use a dictionary with the input parameter(s) as keys and the outputs as values. So every time a function is called it first checks whether the inputs exists in the cache if it does it returns the value else it computes the new output for the new input, updates the cache with the new input then it returns the output. Let see some examples now:

Running this program with the input of 35, fibonacci(35), it took an average of 15seconds to compute every time, though the output is sure to remain the same that is 9227465 for every run. What if we can store this results so that we don’t need to re-compute it again but rather and grab and use the result, that where Memoization comes in.

Running the second program this time around, same fibonacci(35), it took an average of just 60microseconds to compute for the first time and just 2 microseconds for all subsequent calls of the function. You might have expected the first call to have taken 15seconds, this isn’t so because the Fibonacci function works by calling itself repeatedly and since from our function we are caching every value if it is new, we end up re-computing the same input values over again. See the diagram below for how Fibonacci recursion calls work.

Now let implement it using decorator function:

Now running the program this time around, same fibonacci(35), it took an average of just 15seconds to compute for the first time as expected and just 2.5 microseconds on average for all subsequent calls of the function. This is because the decorator function caches only the final output and not all outputs along the computing line but all subsequent calls are all done in constant time.

Related posts:

Satoshi Nakamoto is the name used by the unknown person or people who designed bitcoin and created its original reference implementation. In 2008, Satoshi Nakamoto published Bitcoin: A Peer-to-Peer…

Mike Newman was an Australian who headed off to Europe with two Sydney Uni mates in a Morris Minor. He appeared in Bazza McKenzie holds his own, was Warden of the Working Men’s College before…