PYTHON
Build a Simple LRU Cache with Python's OrderedDict
Implement a basic Least Recently Used (LRU) cache in Python using `collections.OrderedDict` to efficiently manage limited-size caches in web applications for performance optimization.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: str) -> str:
if key not in self.cache:
return "-1" # Or raise KeyError
# 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: 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 (the first item)
self.cache.popitem(last=False)
self.cache[key] = value
self.cache.move_to_end(key) # Newly added item is also most recently used
# Example Usage:
lru_cache = LRUCache(3)
lru_cache.put('user_1', 'John Doe')
lru_cache.put('user_2', 'Jane Smith')
lru_cache.put('user_3', 'Peter Jones')
print(f"Cache: {list(lru_cache.cache.items())}")
lru_cache.get('user_2') # 'user_2' becomes most recently used
print(f"Cache after getting 'user_2': {list(lru_cache.cache.items())}")
lru_cache.put('user_4', 'Alice Brown') # 'user_1' is evicted
print(f"Cache after putting 'user_4': {list(lru_cache.cache.items())}")
print(f"Get 'user_1': {lru_cache.get('user_1')}") # Should be -1
How it works: An LRU (Least Recently Used) cache is a common strategy to manage a limited-size cache by evicting the least recently used items when the cache is full. `collections.OrderedDict` is perfect for this as it remembers the order in which items were inserted. When an item is accessed (`get`), we move it to the end. When a new item is added (`put`) and the cache is full, we remove the first item (the least recently used) before adding the new item to the end. This structure is highly beneficial for caching frequently accessed data in web applications.