LRU Cache¶
An LRU (Least Recently Used) cache evicts the oldest unused entry when it hits capacity. It's the go-to caching strategy for model inference servers, feature stores, and any system where recent access is a good predictor of future access.
Problem¶
Implement a cache with a fixed capacity that supports:
- get(key), return the value if present, otherwise
None - set(key, value), insert or update; evict the least recently used entry if at capacity
- delete(key), remove an entry
All operations should be O(1).
Approach¶
Dict + List: Use a dictionary for O(1) lookups and a list to track access order. On every get or set, move the key to the end of the list. On eviction, pop from the front. The catch: list.remove(key) is O(n), so this approach is fine for small caches but degrades at scale.
OrderedDict: Python's OrderedDict gives you move_to_end() and popitem(last=False), both O(1). This is the clean, production-grade solution.
Implementation¶
Dict + List¶
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.order = []
def get(self, key):
if key not in self.cache:
return None
self.order.remove(key)
self.order.append(key)
return self.cache[key]
def set(self, key, value):
if key in self.cache:
self.order.remove(key)
elif len(self.cache) == self.capacity:
evicted = self.order.pop(0)
del self.cache[evicted]
self.cache[key] = value
self.order.append(key)
def delete(self, key):
if key in self.cache:
del self.cache[key]
self.order.remove(key)
OrderedDict¶
from collections import OrderedDict
class LRUCacheOrdered:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return None
self.cache.move_to_end(key)
return self.cache[key]
def set(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
def delete(self, key):
self.cache.pop(key, None)
Complexity¶
| Approach | get | set | delete |
|---|---|---|---|
| Dict + List | O(n) | O(n) | O(n) |
| OrderedDict | O(1) | O(1) | O(1) |
Takeaway¶
In production ML systems, LRU caches sit in front of expensive operations, embedding lookups, tokenization results, model predictions for repeated inputs. The OrderedDict version gives you O(1) across the board with no external dependencies. For distributed settings you'd reach for Redis or Memcached, but the eviction logic is the same.