PYTHON
Implement a Simple LRU Cache with Python Dictionaries
Create a basic Least Recently Used (LRU) cache in Python leveraging dictionary's order-preserving property, useful for optimizing data retrieval and reducing redundant computations in web services.
class LRUCache:
def __init__(self, capacity: int):
self.cache = {}
self.capacity = capacity
def get(self, key: str) -> str:
if key not in self.cache:
return "Not Found"
# Move the accessed key to the end to mark it as recently used
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key: str, value: str) -> None:
if key in self.cache:
# Key exists, update value and move to end
self.cache.pop(key)
elif len(self.cache) >= self.capacity:
# Cache full, remove the least recently used item (first item)
lru_key = next(iter(self.cache))
self.cache.pop(lru_key)
self.cache[key] = value
def __repr__(self):
return str(self.cache)
# Example Usage
lru_cache = LRUCache(capacity=3)
lru_cache.put("user_1", "Alice")
lru_cache.put("user_2", "Bob")
lru_cache.put("user_3", "Charlie")
print(f"Cache after initial puts: {lru_cache}")
lru_cache.get("user_1") # Access user_1, makes it recently used
print(f"Cache after accessing user_1: {lru_cache}")
lru_cache.put("user_4", "David") # Cache is full, user_2 (LRU) should be evicted
print(f"Cache after putting user_4: {lru_cache}")
print(f"Get user_2: {lru_cache.get('user_2')}") # Should be 'Not Found'
How it works: A Least Recently Used (LRU) cache is a caching strategy that discards the least recently used items when the cache is full. This snippet implements a simple LRU cache in Python using a standard dictionary. In Python 3.7+, dictionaries preserve insertion order, allowing us to treat the dict's beginning as LRU and its end as MRU. Accessing or adding an item updates its position to the end, while putting a new item when the cache is full removes the item at the beginning (LRU). This is vital for performance optimization in web applications by storing frequently accessed data in memory.