Challenge: an LRU cache

A cache keeps answers that were slow to get, so that asking again is fast: pages a browser downloaded, rows a program read from a database. A cache can't keep everything, so when it's full, something has to go. A least recently used (LRU) cache throws out the item that was used longest ago, betting that what you used lately you'll use again soon. It's a favorite interview question because it needs two things in O(1) at once: finding an item by its key, and finding the oldest one.

A dict remembers its order

A dict keeps its keys in the order they were added. (Its table holds only positions, and the pairs themselves sit in a list in the order they came.) Giving a key that's already there a new value keeps its place; removing the key and adding it again moves it to the end:

>>> weather = {"Oslo": 4, "Lima": 19, "Rome": 15}
>>> weather["Oslo"] = 6
>>> list(weather)
['Oslo', 'Lima', 'Rome']
>>> temp = weather.pop("Oslo")
>>> weather["Oslo"] = temp
>>> list(weather)
['Lima', 'Rome', 'Oslo']

So the order of a dict can be the order of use: the most recent key at the end, the oldest at the front.

OrderedDict

collections.OrderedDict is a dict made for exactly this. move_to_end(key) moves a key to the end, and popitem(last=False) removes the first pair, the oldest, and returns it. Both are O(1) on average: move_to_end finds the key by its hash, as a dict does, and popitem(last=False) takes the first key in the order and deletes it from the table, like del.

from collections import OrderedDict

weather = OrderedDict()
for city, temp in [("Oslo", 4), ("Lima", 19), ("Rome", 15)]:
    weather[city] = temp
weather.move_to_end("Oslo")
print(list(weather))
print(weather.popitem(last=False))
print(list(weather))

['Lima', 'Rome', 'Oslo']
('Lima', 19)
['Rome', 'Oslo']

Beside its hash table, an OrderedDict keeps its keys in a chain where each key knows the one before it and the one after it, so it can take a key out of the middle and put it at the end without moving anything else. Such a chain is called a doubly linked list. An interviewer may ask you to build the cache without OrderedDict, from a plain dict and a doubly linked list of your own, which is what OrderedDict does inside: the dict finds a key's link in the chain, and the link comes out and goes to the end in O(1). The module on trees builds a linked list. A plain dict's oldest key is next(iter(d)), but each key removed from the front leaves an empty place that iteration has to skip until the dict is rebuilt, so taking the oldest out again and again can get slow. For a cache, use OrderedDict.

The cache

With the most recently used key at the end:

• get(key): if the key is in the cache, move it to the end, since it was just used, and return its value. Otherwise return None.
• put(key, value): store the value and move the key to the end. If the cache now holds more than capacity keys, remove the oldest one, at the front.

Each step is an O(1) dict operation, so both methods are O(1) on average, and the cache needs O(capacity) memory. The slow way keeps the order in a list, where order.remove(key) searches the list: O(capacity) for every get.

functools.lru_cache

Python has an LRU cache for functions. @lru_cache(maxsize=...) above a function wraps it, the way @property wraps a method: a call with arguments seen before returns the stored result without running the function, and once maxsize results are stored, a new one pushes out the least recently used. cache_info() counts the hits (answers from the cache) and the misses:

from functools import lru_cache


@lru_cache(maxsize=2)
def slow_square(n):
    print("working out", n)
    return n * n


for n in [3, 4, 3, 5, 4]:
    slow_square(n)
print(slow_square.cache_info())

working out 3
working out 4
working out 5
working out 4
CacheInfo(hits=1, misses=4, maxsize=2, currsize=2)

The second 3 is a hit and makes 3 the most recent, so 5 pushes out 4, and the last call has to work 4 out again. With maxsize=None the cache never forgets (functools.cache is the same), which is memoization: a recursive function such as Fibonacci then works out each number only once. The arguments become keys of a dict inside, so they must be hashable: a list argument stops with TypeError: unhashable type: 'list'.