PYTHON
Simple LRU Cache with OrderedDict
Implement a basic Least Recently Used (LRU) cache in Python using `collections.OrderedDict` for efficient memory management of frequently accessed or computed data.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: str) -> any:
if key not in self.cache:
return -1 # Or raise KeyError, depending on desired behavior
value = self.cache.pop(key)
self.cache[key] = value # Move to the end (most recently used)
return value
def put(self, key: str, value: any) -> None:
if key in self.cache:
self.cache.pop(key)
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # Remove the first (least recently used)
self.cache[key] = value # Add or update at the end
# Example Usage:
lru_cache = LRUCache(capacity=3)
lru_cache.put("a", 1)
lru_cache.put("b", 2)
lru_cache.put("c", 3)
print(f"Cache after initial puts: {list(lru_cache.cache.items())}") # Output: [('a', 1), ('b', 2), ('c', 3)]
lru_cache.get("b") # 'b' becomes most recently used
print(f"Cache after getting 'b': {list(lru_cache.cache.items())}") # Output: [('a', 1), ('c', 3), ('b', 2)]
lru_cache.put("d", 4) # 'a' is least recently used, so it's removed
print(f"Cache after putting 'd': {list(lru_cache.cache.items())}") # Output: [('c', 3), ('b', 2), ('d', 4)]
print(f"Get 'a': {lru_cache.get('a')}") # Output: Get 'a': -1 (not found)
print(f"Get 'b': {lru_cache.get('b')}") # Output: Get 'b': 2
How it works: An LRU (Least Recently Used) cache evicts the item that has been used the least recently when the cache reaches its capacity. This Python snippet implements a simple LRU cache using `collections.OrderedDict`. `OrderedDict` maintains insertion order, which is key here. When an item is accessed (`get`), it's moved to the end (most recently used). When a new item is added (`put`) and the cache is full, the item at the beginning (least recently used) is removed using `popitem(last=False)`. This provides an efficient way to manage a fixed-size cache.