A Least Recently Used Cache is an efficient data structure we can use to figure out which item in a cache we should remove (evict) when the cache is full. We use Caches to gain quick access to items that are recently used, but cache sizes cannot be infinite. Therefore we need an efficient way to remove (evict) an item used the least, in order to add a new item to the cache to avoid having the cache grow beyond its desired capacity. The goal for the implementation should be O(1) access to the least recently used item for maximum efficiency.
Thanks to Python’s Ordered Dictionary we can implement a LRU Cache with just a few lines of code. The minimum definition of a LRU Cache should contain ‘get‘ and ‘put‘ methods. These methods allow us to retrieve and add to the cache respectively.
First we need to import the OrderedDict collection type from Python’s built in collections package and add a “constructor” for our class, so in Python parlance we have:
from collections import OrderedDict class LRUCache(object): def __init__(self, capacity): self.cache = OrderedDict() self.capacity = capacity
So for example if our class is called LRUCache we would instantiate it like this:
cache = LRUCache(64)
Which means we’ve created an LRUCache that can hold 64 items.
Back to our LRUCache implementation, here is the ‘get’ method, which will return the specific item referenced by the key or -1 if not found:
def get(self, key): if key not in self.cache: return -1 else: self.cache.move_to_end(key) return self.cache[key]
The only argument is the key to the item we wish to retrieve. We first check to see if the key is in the cache (which is a Python OrderedDict). If it is not in the cache we return -1. Otherwise, we move the key to the end of the OrderedDict to show it was recently used.
If that seems confusing, think of the cache as a linked list with the most recently accessed item at the end (tail) of the list and least recently accessed item at the front (head) of the list.
For languages that support pointers, such as C or C++, we could use a linked list along with a hash table to give us O(1) access. But with Python, we get essentially a list AND a hash table with the OrderedDict collection type.
Moving on, here is the ‘put’ method of our Python LRU Cache class which adds an item to the cache:
def put(self, key, value): self.cache[key] = value self.cache.move_to_end(key) if len(self.cache) > self.capacity: self.cache.popitem(last = False)
The arguments are the key and a value. First we add the value to the cache using the typical Python dictionary syntax. Then we move the key to the end of the collection to show it was the recently used item. Next we check the length of the cache against the capacity we were given in the “constructor”. If we’ve exceeded the capacity after adding this item we remove (evict) the item from the front of the collection (the least recently used item) using the popitem method.
Here is the entire Python class:
''' @author: charles newman https://github.com/26point2Newms ''' from collections import OrderedDict class LRUCache(object): ''' Implementation of a Least Recently Used Cache (LRU Cache) which discards the least recently used items first. ''' def __init__(self, capacity): self.cache = OrderedDict() self.capacity = capacity def get(self, key): ''' Returns the value associated with the key if found (cache hit) and moves the key to the end to show it was recently used. Returns -1 if the key is not found (cache miss). ''' if key not in self.cache: return -1 else: self.cache.move_to_end(key) return self.cache[key] def put(self, key, value): ''' Adds/updates the value and moves the key to the end to show it was recently used. Checks the length of the ordered dictionary against the capacity specified in the 'constructor'. Remove the first key (the least recently used) if capacity is exceeded. ''' self.cache[key] = value self.cache.move_to_end(key) if len(self.cache) > self.capacity: self.cache.popitem(last = False)
You can also find this LRU Cache class on my GitHub along with a unit test you can run to see how it functions. If you run it with a debugger you see items being added and removed from their proper place.