PYTHON
Implement a Least Recently Used (LRU) Cache in Python
Optimize web application performance by implementing a Least Recently Used (LRU) cache using Python's collections.OrderedDict for efficient data retrieval and management.
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
value = self.cache.pop(key)
self.cache[key] = value # Move to end (most recently used)
return value
def put(self, key: str, value: any) -> None:
if key in self.cache:
self.cache.pop(key) # Remove existing to update position
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # Remove LRU item
self.cache[key] = value # Add or update as most recently used
# Example Usage:
# lru_cache = LRUCache(2)
# lru_cache.put("key1", "value1")
# lru_cache.put("key2", "value2")
# print(lru_cache.get("key1")) # Output: value1 (key1 becomes MRU)
# lru_cache.put("key3", "value3") # key2 is evicted
# print(lru_cache.get("key2")) # Output: -1
How it works: This snippet implements an LRU cache, a crucial pattern for web performance. It leverages Python's `collections.OrderedDict`, which maintains the order of item insertion. When an item is accessed (`get`), it's moved to the end of the dictionary, marking it as most recently used. If a new item is added (`put`) and the cache is at capacity, the least recently used item (the first item in the `OrderedDict`) is removed before adding the new item to the end.