PYTHON
Building an LRU Cache with `collections.OrderedDict`
Implement a basic Least Recently Used (LRU) cache in Python using `collections.OrderedDict` for efficient memoization, improving web application performance by storing and retrieving frequently accessed data.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: str):
if key not in self.cache:
return -1 # Key not found
# Move the accessed key to the end (most recently used)
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: str, value: any):
if key in self.cache:
# If key exists, update value and move to end
self.cache[key] = value
self.cache.move_to_end(key)
else:
# Add new key-value pair
self.cache[key] = value
if len(self.cache) > self.capacity:
# If cache exceeds capacity, remove the least recently used item (first item)
self.cache.popitem(last=False)
def __repr__(self):
return f"LRUCache(capacity={self.capacity}, cache={list(self.cache.items())})"
# Example Usage
lru = LRUCache(2)
lru.put('user_id_1', {'name': 'Alice', 'email': '[email protected]'})
print(f"After put user_id_1: {lru}")
lru.put('product_id_A', {'name': 'Laptop X', 'price': 1200})
print(f"After put product_id_A: {lru}")
print(f"Get user_id_1: {lru.get('user_id_1')}") # Accesses user_id_1, makes it MRU
print(f"After get user_id_1: {lru}")
lru.put('order_id_101', {'status': 'pending'})
print(f"After put order_id_101 (product_id_A should be evicted): {lru}")
print(f"Get product_id_A: {lru.get('product_id_A')}") # Should return -1 (not found)
print(f"Get user_id_1 again: {lru.get('user_id_1')}")
print(f"Final cache state: {lru}")
How it works: An LRU (Least Recently Used) cache evicts the least recently used items when the cache reaches its capacity. This snippet implements a basic LRU cache using Python's `collections.OrderedDict`. `OrderedDict` maintains insertion order, which is key here. When an item is accessed (`get`), it's moved to the end of the dictionary (marking it as most recently used). When a new item is added (`put`) and the cache is full, the item at the beginning (least recently used) is removed. This pattern is invaluable for caching database query results, API responses, or computationally expensive function calls in web applications, significantly improving performance.