PYTHON
Implement a Simple LRU Cache with collections.OrderedDict
Build an efficient Least Recently Used (LRU) cache in Python using collections.OrderedDict to store a limited number of items, optimizing data retrieval for web applications.
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
value = self.cache.pop(key) # Remove and re-insert to mark as recently used
self.cache[key] = value
return value
def put(self, key: str, value: str) -> None:
if key in self.cache:
self.cache.pop(key) # Key already exists, move to end
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # Evict LRU item (first item)
self.cache[key] = value
# Example usage
lru_cache = LRUCache(2)
lru_cache.put('user1', 'dataA')
lru_cache.put('user2', 'dataB')
print(f"Cache after two puts: {list(lru_cache.cache.items())}")
lru_cache.get('user1') # Access user1, making it most recently used
print(f"Cache after getting user1: {list(lru_cache.cache.items())}")
lru_cache.put('user3', 'dataC') # user2 is now LRU and will be evicted
print(f"Cache after putting user3: {list(lru_cache.cache.items())}")
print(f"Attempt to get evicted user2: {lru_cache.get('user2')}")
How it works: An LRU (Least Recently Used) cache is a caching algorithm that discards the least recently used items when the cache reaches its capacity. `collections.OrderedDict` is ideal for this because it maintains insertion order and provides `popitem()` and `move_to_end()` methods. By removing and re-inserting an accessed item, or evicting the oldest item using `popitem(last=False)`, we efficiently manage the cache's capacity and ensure frequently accessed data remains available.