PYTHON
Build an LRU Cache with `collections.OrderedDict`
Create a basic Least Recently Used (LRU) cache using Python's `collections.OrderedDict` for efficiently storing and retrieving data with a fixed size limit.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: str) -> str | None:
if key not in self.cache:
return None
# Move the accessed key to the end to mark it as most recently used
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: str, value: str) -> None:
if key in self.cache:
# Update value and move to end
self.cache[key] = value
self.cache.move_to_end(key)
else:
if len(self.cache) >= self.capacity:
# Remove the least recently used item (first item)
self.cache.popitem(last=False)
self.cache[key] = value
self.cache.move_to_end(key) # Newly added item is MRU
# Example usage
cache = LRUCache(capacity=3)
cache.put("user:1", "Alice")
cache.put("user:2", "Bob")
cache.put("user:3", "Charlie")
print(f"Cache content: {list(cache.cache.items())}") # [(user:1, Alice), (user:2, Bob), (user:3, Charlie)]
print(f"Get user:2: {cache.get('user:2')}") # user:2 becomes MRU
print(f"Cache content: {list(cache.cache.items())}") # [(user:1, Alice), (user:3, Charlie), (user:2, Bob)]
cache.put("user:4", "David") # user:1 (LRU) will be evicted
print(f"Cache content after adding user:4: {list(cache.cache.items())}") # [(user:3, Charlie), (user:2, Bob), (user:4, David)]
print(f"Get user:1: {cache.get('user:1')}") # Returns None
How it works: An LRU (Least Recently Used) cache is a common caching strategy where the least recently accessed items are removed first when the cache reaches its capacity. This snippet demonstrates how to implement a basic LRU cache using `collections.OrderedDict`. `OrderedDict` maintains insertion order, allowing `popitem(last=False)` to efficiently remove the oldest (LRU) item and `move_to_end()` to update an item's recency status, making it perfect for optimizing expensive operations in web applications.