PYTHON
Build a Basic LRU Cache with Python OrderedDict
Create a Least Recently Used (LRU) cache in Python using `collections.OrderedDict` for efficient retrieval and eviction of items based on access order.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict() # Stores key-value pairs
self.capacity = capacity
def get(self, key: str) -> any:
if key not in self.cache:
return -1 # Not found
# Move the accessed item to the end (most recently used)
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key: str, value: any) -> None:
if key in self.cache:
self.cache.pop(key) # Remove existing to update its position
elif len(self.cache) >= self.capacity:
# If cache is full, evict the LRU item (first item)
self.cache.popitem(last=False)
self.cache[key] = value # Add or update as most recently used
# Example Usage:
lru_cache = LRUCache(3)
lru_cache.put('a', 1)
lru_cache.put('b', 2)
lru_cache.put('c', 3)
print(f"Cache after put(a,1), put(b,2), put(c,3): {list(lru_cache.cache.items())}")
lru_cache.get('b') # 'b' becomes most recently used
print(f"Cache after get('b'): {list(lru_cache.cache.items())}") # Expected: [('a',1), ('c',3), ('b',2)]
lru_cache.put('d', 4) # Cache is full, 'a' (LRU) should be evicted
print(f"Cache after put('d',4): {list(lru_cache.cache.items())}") # Expected: [('c',3), ('b',2), ('d',4)]
print(f"Get 'a': {lru_cache.get('a')}") # Should be -1
print(f"Get 'b': {lru_cache.get('b')}") # Should be 2
How it works: An LRU (Least Recently Used) cache evicts the least recently used item when it reaches its capacity. Python's `collections.OrderedDict` is perfect for implementing a basic LRU cache because it remembers the order in which items were inserted. When an item is accessed (get) or updated (put), we remove it and re-insert it at the end, making it the most recently used. When the cache is full and a new item needs to be added, we use `popitem(last=False)` to remove the first (least recently used) item.