LRU Cache via OrderedDict
An LRU (least-recently-used) cache evicts whichever entry has been untouched the longest when it hits its capacity. `collections.OrderedDict` makes the implementation tiny: `move_to_end` keeps the most-recently-used key at the back, and `popitem(last=False)` evicts the front. This entry covers the get/put loop, the `@functools.lru_cache` shortcut, and a mini benchmark.
221 views
5
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
if capacity <= 0:
raise ValueError('capacity must be positive')
self.capacity = capacity
self.store = OrderedDict()
def get(self, key):
if key not in self.store:
return None
self.store.move_to_end(key) # mark recently used
return self.store[key]
def put(self, key, value):
if key in self.store:
self.store.move_to_end(key)
self.store[key] = value
if len(self.store) > self.capacity:
self.store.popitem(last=False) # evict the LRU front entry
def __repr__(self):
return f'LRUCache({list(self.store.items())})'
cache = LRUCache(capacity=3)
cache.put('a', 1)
cache.put('b', 2)
cache.put('c', 3)
print(cache) # LRUCache([('a', 1), ('b', 2), ('c', 3)])
cache.get('a') # touch 'a'; now 'b' is the LRU.
cache.put('d', 4) # evicts 'b'.
print(cache) # LRUCache([('c', 3), ('a', 1), ('d', 4)])
print(cache.get('b')) # None (evicted)
print(cache.get('a')) # 1OrderedDict keeps insertion order AND lets you mutate that order in O(1). move_to_end(key) lifts a key to the back of the dict; popitem(last=False) removes the front item. Together they implement LRU semantics: every get and successful put lifts its key, and any put that pushes past capacity removes the least-recently-touched front entry. Because both operations are O(1), the cache scales: 100K entries with 1M operations stays well under a second.
from functools import lru_cache
import time
@lru_cache(maxsize=128)
def slow_fib(n):
"""Naive recursive Fibonacci; without the cache this is exponential."""
if n < 2:
return n
return slow_fib(n - 1) + slow_fib(n - 2)
t0 = time.perf_counter()
result = slow_fib(40)
elapsed = time.perf_counter() - t0
print('fib(40):', result, f'in {elapsed * 1000:.2f} ms')
print('cache stats:', slow_fib.cache_info())
# CacheInfo(hits=38, misses=41, maxsize=128, currsize=41)
# Inspect and clear the cache like any other state.
slow_fib.cache_clear()
print('after clear:', slow_fib.cache_info())
# 3.9+: @cache is unbounded lru_cache(maxsize=None) for true memoization.
from functools import cache
@cache
def ack(m, n):
if m == 0:
return n + 1
if n == 0:
return ack(m - 1, 1)
return ack(m - 1, ack(m, n - 1))
print(ack(3, 4)) # 125functools.lru_cache(maxsize=N) is the production answer 95% of the time: thread-safe, written in C, and as fast as you will ever match in pure Python. It memoizes calls keyed by argument values, so the function must take hashable arguments and return values that depend only on its inputs. cache_info() exposes hit / miss counts so you can confirm the cache is actually helping. Reach for the LRUCache class only when you need keys that are not function arguments (HTTP responses by URL, image thumbnails by id), or when you want to expose the cache as a first-class object.
from collections import OrderedDict
import random
import time
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.store = OrderedDict()
def get(self, key):
if key not in self.store:
return None
self.store.move_to_end(key)
return self.store[key]
def put(self, key, value):
if key in self.store:
self.store.move_to_end(key)
self.store[key] = value
if len(self.store) > self.capacity:
self.store.popitem(last=False)
random.seed(42)
cache = LRUCache(capacity=1024)
N = 200_000
keys = [random.randint(0, 2048) for _ in range(N)]
t0 = time.perf_counter()
for k in keys:
if cache.get(k) is None:
cache.put(k, k * k)
elapsed = time.perf_counter() - t0
print(f'{N} mixed get/put ops in {elapsed * 1000:.0f} ms')
print('final cache size:', len(cache.store))
print('a few entries: ', list(cache.store.items())[-3:])200K mixed get/put operations should complete in well under a second on any modern machine, which is what 'O(1) per op' buys you. If you replace OrderedDict with a plain list and shuffle entries on every access, the same workload becomes O(n) per op and runs orders of magnitude slower. Always benchmark caches against your actual workload distribution: random access, hot-key access, and scan-once-then-discard all stress LRU differently. The right capacity is usually 'hot working set + 20% headroom', and the right metric is hit rate, not ops per second.