Caches: LRU with OrderedDict and functools

Remembering what is likely to be needed again

A cache stores results so that repeated requests are fast. Because memory is limited, a cache needs an eviction policy; least recently used (LRU) evicts the entry that has gone unused the longest, a good default for many workloads. A classic LRU cache achieves O(1) get and put by combining a hash map (key to node) with a doubly linked list ordered by recency: on access, move the node to the front; on overflow, remove from the back. In Python, collections.OrderedDict provides both pieces: move_to_end(key) marks an entry as recently used and popitem(last=False) evicts the oldest. For caching function results, the standard library offers functools.lru_cache(maxsize=...) and functools.cache (unbounded, Python 3.9+), with cache_info() statistics and cache_clear(). Arguments must be hashable. Be careful with methods (the cache holds references to self), with mutable return values (callers can modify the cached object) and with functions whose results change over time; for expiring entries, use a TTL cache such as those in the cachetools library.

An LRU cache class and lru_cache on a function

OrderedDict for O(1) LRU, and memoising an expensive function.

from collections import OrderedDict
from functools import lru_cache

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data: OrderedDict[str, str] = OrderedDict()

    def get(self, key: str) -> str | None:
        if key not in self.data:
            return None
        self.data.move_to_end(key)                  # mark as most recently used
        return self.data[key]

    def put(self, key: str, value: str) -> None:
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)           # evict the least recently used

cache = LRUCache(2)
cache.put("user:1", "Asha")
cache.put("user:2", "Ravi")
cache.get("user:1")                                 # user:1 is now most recent
cache.put("user:3", "Meera")                        # evicts user:2
print(list(cache.data))                             # ['user:1', 'user:3']

@lru_cache(maxsize=1024)
def shipping_quote(pincode: str, weight_grams: int) -> int:
    # imagine a slow API call or heavy computation here
    zone = int(pincode[0])
    return 4000 + zone * 500 + (weight_grams // 500) * 1500

print(shipping_quote("411001", 1200))               # computed: 4000 + 2000 + 3000 = 9000
print(shipping_quote("411001", 1200))               # served from the cache
print(shipping_quote.cache_info())                  # hits=1, misses=1, maxsize=1024, currsize=1

The front of your desk

An LRU cache is a small desk: papers you touched recently stay on top, and when the desk is full, the paper at the bottom of the pile (untouched the longest) goes back to the filing cabinet.

Quick check: Which two OrderedDict methods make an O(1) LRU cache straightforward?

• sort and reverse
• append and pop(0)
• keys and values
• move_to_end and popitem(last=False)