PYTHON
Implementing a Simple LRU Cache with OrderedDict
Build a basic Least Recently Used (LRU) cache in Python using `collections.OrderedDict` to manage cached items based on their access frequency, optimizing resource usage.
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 "Not Found"
# 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 (first item)
self.cache.popitem(last=False)
self.cache[key] = value
self.cache.move_to_end(key) # Newly added item is most recently used
# Example Usage:
# lru_cache = LRUCache(capacity=3)
# lru_cache.put("user1", "Alice")
# lru_cache.put("user2", "Bob")
# lru_cache.put("user3", "Charlie")
# print(lru_cache.get("user2")) # Bob (moves user2 to end)
# lru_cache.put("user4", "David") # Evicts user1
# print(lru_cache.get("user1")) # Not Found
# print(lru_cache.cache) # OrderedDict([('user3', 'Charlie'), ('user2', 'Bob'), ('user4', 'David')])
How it works: An LRU (Least Recently Used) cache evicts the least recently accessed items first when the cache reaches its capacity, which is crucial for optimizing performance in web applications. Python's `collections.OrderedDict` is ideal for this because it maintains insertion order, and its `move_to_end()` and `popitem(last=False)` methods allow efficient management of access order, making it simple to implement LRU logic.