PYTHON
Implementing a Basic LRU Cache with Python Dictionaries
Build a simple Least Recently Used (LRU) cache in Python using a dictionary to store frequently accessed data, improving performance by avoiding redundant computations or database calls in web services.
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
def get(self, key: str) -> any:
if key not in self.cache:
return -1 # Or raise KeyError
# Move the accessed item to the 'recently used' end
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key: str, value: any) -> None:
if key in self.cache:
self.cache.pop(key) # Remove to re-insert at end
elif len(self.cache) >= self.capacity:
# Remove the least recently used item (first item in Python 3.7+ dict)
lru_key = next(iter(self.cache))
self.cache.pop(lru_key)
self.cache[key] = value
# Example Usage:
lru_cache = LRUCache(3)
lru_cache.put("key1", "value1")
lru_cache.put("key2", "value2")
lru_cache.put("key3", "value3")
print(f"Cache after 3 puts: {lru_cache.cache}") # {key1, key2, key3}
lru_cache.get("key1") # Access key1, it becomes most recently used
print(f"Cache after get('key1'): {lru_cache.cache}") # {key2, key3, key1}
lru_cache.put("key4", "value4") # Cache is full, key2 (LRU) will be removed
print(f"Cache after put('key4'): {lru_cache.cache}") # {key3, key1, key4}
print(f"Get 'key2': {lru_cache.get('key2')}") # -1, not found
print(f"Get 'key1': {lru_cache.get('key1')}") # 'value1'
print(f"Cache after get('key1'): {lru_cache.cache}") # {key3, key4, key1}
How it works: An LRU (Least Recently Used) cache evicts the least recently accessed item when the cache reaches its capacity. This snippet implements a basic LRU cache using a standard Python dictionary. Since Python 3.7, dictionaries preserve insertion order. By leveraging `pop()` to remove an item and then re-inserting it, we effectively move it to the 'most recently used' end. When capacity is reached, `next(iter(self.cache))` reliably retrieves the key of the least recently used item (the first inserted item that hasn't been accessed and re-inserted).