PYTHON
Basic LFU Cache using collections.Counter
Implement a simple Least Frequently Used (LFU) cache in Python using `collections.Counter` to track access frequencies and `dict` for efficient storage and eviction logic.
from collections import Counter
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.frequencies = Counter() # Tracks frequency of key access
def get(self, key: str) -> str:
if key not in self.cache:
return "NOT_FOUND"
self.frequencies[key] += 1 # Increment frequency
return self.cache[key]
def put(self, key: str, value: str):
if self.capacity == 0:
return
if key in self.cache:
self.cache[key] = value
self.frequencies[key] += 1
return
if len(self.cache) >= self.capacity:
# Evict LFU item. If tie, remove least recently added (approximate)
lfu_key = min(self.frequencies, key=self.frequencies.get)
del self.cache[lfu_key]
del self.frequencies[lfu_key]
self.cache[key] = value
self.frequencies[key] = 1 # New item starts with frequency 1
# Example Usage
lfu = LFUCache(2)
lfu.put("key1", "value1")
lfu.put("key2", "value2")
print(f"Get key1: {lfu.get("key1")}") # Access key1, freq(key1)=2
lfu.put("key3", "value3") # Cache is full, evict key2 (freq 1) over key1 (freq 2)
print(f"Get key2: {lfu.get("key2")}") # Should be NOT_FOUND
print(f"Get key3: {lfu.get("key3")}") # Access key3, freq(key3)=2
print(f"Get key1: {lfu.get("key1")}") # Access key1, freq(key1)=3
lfu.put("key4", "value4") # Cache is full. Evict key3 (freq 2) over key1 (freq 3)
print(f"Get key3: {lfu.get("key3")}") # Should be NOT_FOUND
# Expected Output:
# Get key1: value1
# Get key2: NOT_FOUND
# Get key3: value3
# Get key1: value1
# Get key3: NOT_FOUND
How it works: This snippet demonstrates a basic Least Frequently Used (LFU) cache. It uses a dictionary (`self.cache`) to store key-value pairs and `collections.Counter` (`self.frequencies`) to keep track of how many times each key is accessed. When the cache reaches its `capacity` and a new item needs to be added, it identifies the key with the minimum access frequency using `min(self.frequencies, key=self.frequencies.get)` and evicts that item before inserting the new one. This approach allows for simple frequency-based eviction.