PYTHON
Implement a Simple LRU Cache
Implement a basic Least Recently Used (LRU) cache in Python using `collections.OrderedDict`. Optimize performance by storing and retrieving frequently accessed data efficiently.
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, or return None
# Move the accessed item to the end (most 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:
self.cache.pop(key) # Remove existing key to update its position
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # Remove LRU item
self.cache[key] = value
# Example Usage:
# cache = LRUCache(2)
# cache.put('k1', 'v1')
# cache.put('k2', 'v2')
# print(cache.get('k1')) # Output: 'v1' (k1 is now MRU)
# cache.put('k3', 'v3') # k2 is evicted (LRU)
# print(cache.get('k2')) # Output: -1
# cache.put('k4', 'v4') # k1 is evicted (LRU)
# print(cache.get('k1')) # Output: -1
# print(cache.get('k3')) # Output: 'v3' (k3 is now MRU)
# print(cache.get('k4')) # Output: 'v4' (k4 is now MRU)
How it works: This snippet demonstrates how to implement a basic Least Recently Used (LRU) cache using Python's `collections.OrderedDict`. An LRU cache stores a fixed number of items and discards the least recently used item when the cache reaches its capacity and a new item needs to be added. `OrderedDict` maintains insertion order, which is key here. When an item is accessed (`get`) or updated (`put`), it's moved to the "end" (most recently used) of the `OrderedDict`. When the cache is full and a new item is inserted, `popitem(last=False)` efficiently removes the item at the "beginning" (least recently used).