PYTHON
Implementing a Basic LRU Cache
Boost performance in your Python web applications with a custom Least Recently Used (LRU) cache, storing data and managing eviction with dictionaries and lists.
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.order = [] # Simulates a linked list for LRU order
def get(self, key):
if key not in self.cache:
return -1
# Move the accessed key to the front to mark as most recently used
self.order.remove(key)
self.order.insert(0, key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.order.remove(key)
elif len(self.cache) >= self.capacity:
# Evict the least recently used item (last item in order list)
lru_key = self.order.pop()
del self.cache[lru_key]
self.cache[key] = value
self.order.insert(0, key) # Mark as most recently used
def __str__(self):
return f"Cache: {self.cache}, Order: {self.order}"
# Example Usage:
cache = LRUCache(2)
cache.put(1, 1)
print(cache) # Cache: {1: 1}, Order: [1]
cache.put(2, 2)
print(cache) # Cache: {1: 1, 2: 2}, Order: [2, 1]
cache.get(1)
print(cache) # Cache: {1: 1, 2: 2}, Order: [1, 2] (1 is now MRU)
cache.put(3, 3) # Evicts key 2 (LRU)
print(cache) # Cache: {1: 1, 3: 3}, Order: [3, 1]
cache.get(2)
print(cache) # Output: -1 (2 is not in cache)
How it works: This snippet provides a basic implementation of a Least Recently Used (LRU) cache, a crucial component for optimizing performance in web applications by storing frequently accessed data. It uses a dictionary (`self.cache`) to quickly retrieve values by key and a list (`self.order`) to maintain the usage order. When an item is accessed or added, it's moved to the front of the `order` list. If the cache reaches its capacity, the item at the end of the `order` list (the LRU item) is evicted to make space for new data. This prevents the cache from growing indefinitely and ensures relevant data is prioritized.