PYTHON
Build a Simple LRU Cache with `collections.OrderedDict`
Learn to implement a basic Least Recently Used (LRU) cache in Python using `collections.OrderedDict` to efficiently manage and retrieve frequently accessed data, optimizing performance.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: str) -> int:
if key not in self.cache:
return -1
# Move the accessed key to the end to mark it as most recently used
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: str, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key) # Mark as recently used
self.cache[key] = value
if len(self.cache) > self.capacity:
# Pop the first item (least recently used)
self.cache.popitem(last=False)
# Example Usage:
cache = LRUCache(2)
cache.put("user:1", 100)
cache.put("user:2", 200)
print(cache.get("user:1")) # Output: 100 (user:1 is now most recently used)
cache.put("user:3", 300) # Evicts user:2 (least recently used)
print(cache.get("user:2")) # Output: -1 (not found)
cache.put("user:4", 400) # Evicts user:1
print(cache.get("user:1")) # Output: -1
print(cache.get("user:3")) # Output: 300
How it works: A Least Recently Used (LRU) cache is a caching strategy that discards the least recently used items first when the cache reaches its capacity. Python's `collections.OrderedDict` is perfect for this as it remembers the order in which items were inserted. By using `move_to_end()` on access (`get`) or insertion (`put`), we can efficiently maintain the usage order. When the cache exceeds its `capacity`, `popitem(last=False)` removes the item added earliest (the least recently used one), ensuring the cache stays within its size limit while prioritizing fresh data.