PYTHON
Implementing a Simple Fixed-Size Cache with collections.deque
Learn to create an efficient fixed-size, in-memory cache using Python's collections.deque that automatically evicts the oldest items when capacity is reached.
from collections import deque
class FixedSizeCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = deque(maxlen=capacity)
self.lookup = set() # For O(1) membership testing
def add(self, item):
if item not in self.lookup:
if len(self.cache) == self.capacity:
# Remove the oldest item from the lookup set
oldest_item = self.cache[0]
self.lookup.remove(oldest_item)
self.cache.append(item)
self.lookup.add(item)
return True # Item added
return False # Item already exists
def get_cache_content(self):
return list(self.cache)
# Example Usage
cache = FixedSizeCache(capacity=3)
print(f"Added item 'A': {cache.add('A')}") # True
print(f"Added item 'B': {cache.add('B')}") # True
print(f"Added item 'C': {cache.add('C')}") # True
print(f"Cache content: {cache.get_cache_content()}") # ['A', 'B', 'C']
print(f"Attempting to add 'B' again: {cache.add('B')}") # False (already exists)
print(f"Cache content: {cache.get_cache_content()}") # ['A', 'B', 'C']
print(f"Added item 'D': {cache.add('D')}") # True (evicts 'A')
print(f"Cache content: {cache.get_cache_content()}") # ['B', 'C', 'D']
print(f"Added item 'E': {cache.add('E')}") # True (evicts 'B')
print(f"Cache content: {cache.get_cache_content()}") # ['C', 'D', 'E']
How it works: This snippet demonstrates a simple fixed-size cache using `collections.deque` with a `maxlen`. When the `deque` reaches its maximum size, adding a new item automatically evicts the oldest one. A `set` is used in conjunction with the `deque` to provide O(1) average time complexity for checking if an item already exists in the cache before adding, preventing duplicates and improving efficiency.