PYTHON
Build a Basic LRU Cache with OrderedDict
Create a simple Least Recently Used (LRU) cache in Python using `collections.OrderedDict` to efficiently manage limited-size data storage based on access frequency.
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 # Or raise KeyError
# 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: any) -> 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 is full, remove the first item (least recently used)
self.cache.popitem(last=False)
# Add or update the item at the end
self.cache[key] = value
# Example Usage:
lru_cache = LRUCache(2)
lru_cache.put("apple", 1) # Cache: {"apple": 1}
lru_cache.put("banana", 2) # Cache: {"apple": 1, "banana": 2}
print(f"Get 'apple': {lru_cache.get('apple')}") # Cache: {"banana": 2, "apple": 1}
lru_cache.put("cherry", 3) # Cache is full, "banana" is popped. Cache: {"apple": 1, "cherry": 3}
print(f"Get 'banana': {lru_cache.get('banana')}") # Returns -1
lru_cache.put("date", 4) # Cache is full, "apple" is popped. Cache: {"cherry": 3, "date": 4}
print(f"Current Cache: {list(lru_cache.cache.items())}")
How it works: An LRU (Least Recently Used) cache is a fundamental data structure that stores a fixed number of items, evicting the least recently accessed item when the cache reaches its capacity. This snippet implements an LRU cache using Python's `collections.OrderedDict`. `OrderedDict` maintains insertion order, allowing `popitem(last=False)` to remove the oldest (LRU) item and `pop()` followed by re-insertion to move an accessed item to the end (MRU), ensuring efficient cache management.