Advanced Concepts for Self-taught Devs: Intro to Memoization in Python

Advanced Programming Concepts for Self-taught Beginners

Photo by Sean Lim on Unsplash

Oscar Wilde famously said, “Nothing worth knowing can be taught.” And while he didn’t mean it in this way, it’s certainly true of programming. Learning to program is something that another person can’t teach you; you have to learn it yourself.

Even in a ‘traditional’ college computer science education, hearing lectures about programming doesn’t really teach you to program. You have to do it yourself; you have to build things to learn. This is why self-taught programmers can absolutely be as great at programming as CS majors.

But one of the advantages that CS majors get is exposure to a ton of CS concepts (not the same thing as learning to program) that become valuable when developing software. The coding interview process may be broken, but preparing for it provides self-taught programmers some exposure to these concepts initially. Whether you’re learning because you want to apply for a software engineering role, full-stack web development job, or just curious- these concepts are fun to learn and help instill the right mindset.

Back at my first startup, one of our reoccurring developer interview questions required you to have a basic understanding of anonymous inner classes in Java. I recently saw an article on Jane Street’s blog about a memoization question that used to be in their software engineering interviews. So I think this could be a perfect place to start by tieing these two concepts together.

So what is memoization?

Memoization (from the root word memo or memorandum) is a way of optimizing your code to speed it up. Specifically, it’s a technique of caching results from a function.

Caching is when you store the results of an operation so that it’s ready to go. It’s the same concept as a website and your web browser caching images so that page loads faster.

In programming, memoization refers to caching a function’s output based on the input. Normally we’re talking about deterministic functions, which give the same output for the same input. This typically wouldn’t be something you’d want to do with a nondeterministic function; for example, a function with some pseudo-randomness involved.

Memoization is something you’d want to do when the function is ‘expensive.’ Which means that it takes a lot of resources like computational time and storage. An example might be a function that does some historical data analysis on a stock or a complex calculation on a large data set. You wouldn’t want to do the expensive analysis each time a user wanted that information about a particular stock, especially if many users might be interested in that same stock.

Let’s walk through what this might look like in theory.

Say we have some function f that does some costly calculation. We want to write a function g that memoizes the results. So that g(x) checks to see if we already have f(x) stored first and only if it doesn’t then execute f(x), store the result for the future, and then return the result.

So on a high level, this is the sequence of operations:

1. g(x) -> checks to see if we’ve already done f(x) and have the results stored
2. If we do, it immediately returns the results.
3. If we don’t, it executes f(x)
4. It then caches the result for future use
5. Then, it returns the result.

Now that we understand in theory what’s supposed to happen let’s look at some of the considerations for practically doing this in Python.

To do this, we need to choose a data structure to store the results, and we can leverage decorators in Python to implement a generic function wrapper to make it nice and clean.

To store the cached results, we’re going to use a hash table. In Python, it’s called a dictionary. It’s important to know that a dictionary is a hash table. A hash table is a type of data structure that uses an address or index value as a key mapped to the value being stored- this means that the index value behaves as a key for data value. Dictionaries can also be called “associative arrays.” It works perfectly for our goal because we can use the input of our function as the key and the output result we want to cache as the value.

An example of this would be:

cache = {‘x’ : ‘y’}

where x is the input to our function and y is the output value being stored

You’re thinking, “This all sounds easy so far!” I’m glad. But actually, we need to step back a bit. Before I mentioned decorators, we need to understand a bit more about what they are and why we might need them.

So what is a decorator?

A decorator is the Python implementation of a software design pattern that enables functionality for a function to alter another function, method, or class dynamically. A simple way to think about it is a decorator is a function that takes another function and extends its behavior. Here’s where it gets a bit confusing- the decorator itself isn’t the software design pattern that’s important. The decorator is a nice way to do what we need to do, enabling one function to alter another. The thing we’re actually doing is a Closure.

A Closure is a technique for implementing scoped name binding in first-class functions. This is often associated with the concept of anonymous functions but isn’t strictly the same thing. The software design patterned mentioned before that enables manipulating the scope of the variables inside a function is a closure.

You can read more about closures and anonymous functions here on Wikipedia, the examples they use happen to be in Python.

But what you need to know is that python decorators are a way of easily implementing this concept and reassign the scope of the variables being operated on. It’s a way for an inner function to have an extended scope that includes the outer function variables.

Let’s look at an example:

In this example, the function thisisadecorator() is the decorator. The @ symbol invokes the decorators use.

But it’s critical again to note that decorators are an easy way to doing closures. They aren’t the closure itself. Here’s an example of accomplishing the same outcome without a decorator.

Ok, now let’s put it all together with a real example.

Let’s say we needed to write a recursive function that returned the factorial of a large number.

Simple enough. Now let's implement a cache using a decorator:

So here we have the memorized function memorize(ff) which contains the dictionary “cache”.

The inner function “innerfunc” takes in the number, checks to see if it’s not in the cache. If it is, it just returns the value, if it isn’t it calls the function being passed into the memoize_ff function, referred to here as ff (short for factorialfunc).

The outer function, factorialfunc is decorated with @memoize_ff.

You might need to go back a few times through the code or try implementing it in a Jupyter notebook to see it in action.

Further concepts and reading:

So now that you’ve got the basic concept, think about how optimizing your code could get more complicated. For example, memory usage could be a big issue. But wait- I thought Python manages memory for me!

Yes, but that doesn’t mean that it does it efficiently or that you can’t do things to make your code work more efficiently. For example, you’ll probably need to come up with ways to evict things from the hash table that aren’t used frequently. Maybe you only want to store the last 100 outputs or outputs that are frequently requested.

functools.lru_cache — This is another way of doing this in Python.

timeit — This is a simple way to time your code to see how much it actually improves it.

I hope you enjoyed this article and hopefully, it introduced some interesting new concepts to help you in your learning. If you found this interesting feel free to connect with me on Twitter.