PYTHON
Implementing a Simple LRU Cache using collections.OrderedDict
Build a basic Least Recently Used (LRU) cache in Python for efficient data retrieval by leveraging the `collections.OrderedDict` to manage item access order.
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 None # Or raise KeyError
self.cache.move_to_end(key) # Mark as recently used
return self.cache[key]
def put(self, key: str, value: str):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Remove LRU item
# Example usage:
cache = LRUCache(capacity=2)
cache.put('k1', 'v1')
cache.put('k2', 'v2')
print(f"Get k1: {cache.get('k1')}") # k1 is now most recently used
cache.put('k3', 'v3') # k2 will be removed as it's the LRU item
print(f"Get k2: {cache.get('k2')}") # Should be None
print(f"Cache items: {list(cache.cache.items())}")
# Expected output:
# Get k1: v1
# Get k2: None
# Cache items: [('k1', 'v1'), ('k3', 'v3')]
How it works: An LRU (Least Recently Used) cache is a fundamental optimization technique in web development, used to store frequently accessed data and evict the least recently used items when the cache is full. This snippet implements a simple LRU cache using `collections.OrderedDict`. `OrderedDict` maintains insertion order, and its `move_to_end()` method makes an item the most recently used, while `popitem(last=False)` efficiently removes the oldest (least recently used) item, making it ideal for LRU logic.