For a bit of fun, I wanted to implement a simple LRU cache in Python. Here’s a short walk-through of my thought processes and general steps. This LRU cache is not a full implementation for anything you’d want to use in production, but just the core functionality. I may add more to it in the future though.
If you are looking for a complete LRU cache, consider the following:
Others are also available.
What is an LRU cache?
LRU stands for ‘least recently used’. An LRU cache is a cache which discards its least recently used items when it becomes full.
Some examples are with an LRU cache of size 2 applied to a function called
add which simply adds two numbers together:
Setting up the function decorator
First step is to define how the end-user will interact with the LRU cache.
Typically, this is done via a function decorator. Here’s an example:
So we expect the LRU cache to be used in the following way:
Here we perform the initial setup of our
LRUCache class which is consistent with how we intend to use it. We also stub out an incredibly simple (and incomplete)
call method; it just returns a cached value if the same arguments are used.
The underlying data structure of this LRU cache is a dictionary.
Adding the notion of orderedness
To ensure only a maximum of
N items are cached, we need to add a check after retriving the value.
At the same time, we can switch from using a dictionary to an ordered dictionary. This will allow us to remove the value of the earliest entry.
Note that this is still incorrect - it does not follow the definition of ‘least recently used’.
Removing the correct cached value
pop any already cached value or compute a new value given the arguments. This saves us a few lines of code for the earlier
We then re-insert the value so that the
OrderedDict can update the order internally. This means the
popitem(last=False) will remove the oldest used cache value, thus keeping only the most recently used items.
The eagle-eyed amoungst us will have spotted that we only supported positional arguments earlier; the kwargs dictionary is not hashable so cannot be used as a dictionary key.
In order to create a key, we convert the dictionary into a list of sorted tuples.
We then use this key when getting and setting values in the cache.
Note this is just an extremely naive way of supporting
kwargs. It is quite easy to construct test cases which break this.
Here we present the full implementation of a basic LRU cache.
As previously mentioned, this was just for some fun so its best to use a more fully-featured implementation.