PYTHON
Implement a Simple LRU Cache with Python's OrderedDict
Build a basic Least Recently Used (LRU) cache using Python's `collections.OrderedDict` to efficiently store and retrieve data, optimizing performance for frequently accessed items.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1 # Key not found
# Move the accessed key to the end to mark it as recently used
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.pop(key) # Remove existing key to update its position
elif len(self.cache) >= self.capacity:
# Remove the least recently used item (first item)
self.cache.popitem(last=False)
self.cache[key] = value # Add or update key, placing it at the end
# Example Usage:
lru_cache = LRUCache(capacity=3)
lru_cache.put('itemA', 1)
lru_cache.put('itemB', 2)
lru_cache.put('itemC', 3)
print(f"Cache after put A, B, C: {list(lru_cache.cache.items())}")
lru_cache.get('itemB') # Access B, making it most recently used
print(f"Cache after get B: {list(lru_cache.cache.items())}")
lru_cache.put('itemD', 4) # D is added, itemA (least recently used) is evicted
print(f"Cache after put D: {list(lru_cache.cache.items())}")
print(f"Get itemA (should be -1): {lru_cache.get('itemA')}")
print(f"Get itemC (should be 3): {lru_cache.get('itemC')}")
print(f"Cache after get C: {list(lru_cache.cache.items())}")
How it works: This snippet implements a simple Least Recently Used (LRU) cache using Python's `collections.OrderedDict`. An LRU cache stores a fixed number of items and, when its capacity is reached, it discards the item that hasn't been used for the longest time to make room for new ones. `OrderedDict` is ideal for this because it maintains insertion order, allowing `move_to_end()` to update an item's recency and `popitem(last=False)` to efficiently remove the oldest item. Caching is a fundamental optimization technique in web development to reduce database load, speed up API responses, and improve overall application performance by storing frequently accessed, expensive-to-compute data.