PYTHON
Implementing a Simple LRU Cache with `collections.OrderedDict`
Build an efficient Least Recently Used (LRU) cache in Python using `collections.OrderedDict`. This technique is perfect for caching frequently accessed data in web applications, improving performance by reducing redundant computations or database queries.
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
# Move the accessed item 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:
# Update value and move to end
self.cache[key] = value
self.cache.move_to_end(key)
else:
# Add new item
self.cache[key] = value
# If capacity is exceeded, remove the least recently used item (the first one)
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # popitem(last=False) removes the first item
# Example Usage:
cache = LRUCache(capacity=2)
cache.put("user:1", {"name": "Alice"})
cache.put("user:2", {"name": "Bob"})
# print(f"Cache after initial puts: {list(cache.cache.items())}")
# Expected: [('user:1', {'name': 'Alice'}), ('user:2', {'name': 'Bob'})]
cache.get("user:1") # "user:1" becomes most recently used
# print(f"Cache after getting user:1: {list(cache.cache.items())}")
# Expected: [('user:2', {'name': 'Bob'}), ('user:1', {'name': 'Alice'})]
cache.put("user:3", {"name": "Charlie"}) # Adds "user:3", "user:2" is removed (LRU)
# print(f"Cache after putting user:3: {list(cache.cache.items())}")
# Expected: [('user:1', {'name': 'Alice'}), ('user:3', {'name': 'Charlie'})]
# Trying to get an expired/non-existent item
# print(f"Getting user:2 (should be -1): {cache.get('user:2')}")
# Expected: -1
How it works: An LRU (Least Recently Used) cache is a fundamental pattern for optimizing performance by storing frequently accessed data and evicting the oldest, least used items when the cache reaches its capacity. This snippet demonstrates how to implement a simple LRU cache using Python's `collections.OrderedDict`. `OrderedDict` maintains insertion order, and its `move_to_end()` method efficiently updates an item's recency, while `popitem(last=False)` easily removes the least recently used item (the first one added).