PYTHON
Build a Simple LRU Cache with Python's `collections.OrderedDict`
Implement a basic Least Recently Used (LRU) cache in Python using `collections.OrderedDict` to manage cache entries and evict old items efficiently.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: str) -> str:
if key not in self.cache:
return -1 # Or raise KeyError, or return None
# Move the accessed item 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:
# If key exists, update value and move to end
self.cache[key] = value
self.cache.move_to_end(key)
else:
# If cache is full, remove the least recently used item (first item)
if len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # last=False removes the first (LRU) item
self.cache[key] = value # Add new item
self.cache.move_to_end(key) # Mark as most recently used
def __repr__(self):
return str(self.cache)
# Example Usage:
lru_cache = LRUCache(capacity=3)
lru_cache.put("user1", "Alice")
lru_cache.put("user2", "Bob")
lru_cache.put("user3", "Charlie")
print(f"Cache after initial puts: {lru_cache}")
lru_cache.get("user2") # Access 'user2', making it MRU
print(f"Cache after getting user2: {lru_cache}")
lru_cache.put("user4", "David") # Cache is full, 'user1' should be evicted
print(f"Cache after putting user4: {lru_cache}")
print(f"Get user1: {lru_cache.get('user1')}") # -1 (user1 was evicted)
How it works: An LRU (Least Recently Used) cache evicts the least recently accessed items when the cache reaches its capacity. Python's `collections.OrderedDict` is perfect for this because it maintains insertion order. The `move_to_end()` method makes an item the most recently used. When adding a new item and the cache is full, `popitem(last=False)` removes the item that was added or accessed the longest time ago, ensuring the cache adheres to the LRU policy. This is invaluable for optimizing database queries or API calls by storing frequently accessed results.