108 lines
3.2 KiB
Python
108 lines
3.2 KiB
Python
"""O(1) Least-Frequently-Used cache.
|
|
|
|
Design: each frequency bucket is a doubly-linked list ordered by recency
|
|
(most-recently-used at the head). A node stores key, value, freq. On access
|
|
the node moves from its current bucket to the next-frequency bucket's head.
|
|
min_freq tracks the bucket containing the least-frequent (and among those,
|
|
least-recently-used) node for O(1) eviction.
|
|
"""
|
|
|
|
|
|
class _Node:
|
|
__slots__ = ("key", "value", "freq", "prev", "next")
|
|
|
|
def __init__(self, key, value):
|
|
self.key = key
|
|
self.value = value
|
|
self.freq = 1
|
|
self.prev = None
|
|
self.next = None
|
|
|
|
|
|
class _DLList:
|
|
"""Doubly linked list with sentinel head/tail; most-recent at head side."""
|
|
|
|
__slots__ = ("head", "tail", "size")
|
|
|
|
def __init__(self):
|
|
self.head = _Node(None, None) # sentinel
|
|
self.tail = _Node(None, None) # sentinel
|
|
self.head.next = self.tail
|
|
self.tail.prev = self.head
|
|
self.size = 0
|
|
|
|
def add_front(self, node):
|
|
node.prev = self.head
|
|
node.next = self.head.next
|
|
self.head.next.prev = node
|
|
self.head.next = node
|
|
self.size += 1
|
|
|
|
def remove(self, node):
|
|
node.prev.next = node.next
|
|
node.next.prev = node.prev
|
|
node.prev = None
|
|
node.next = None
|
|
self.size -= 1
|
|
|
|
def pop_tail(self):
|
|
# least recent = node before tail sentinel
|
|
if self.size == 0:
|
|
return None
|
|
node = self.tail.prev
|
|
self.remove(node)
|
|
return node
|
|
|
|
def is_empty(self):
|
|
return self.size == 0
|
|
|
|
|
|
class LFUCache:
|
|
def __init__(self, capacity):
|
|
if capacity < 0:
|
|
raise ValueError("capacity must be non-negative")
|
|
self.capacity = capacity
|
|
self._key = {} # key -> _Node
|
|
self._freq = {} # freq -> _DLList
|
|
self._min_freq = 0
|
|
|
|
def _touch(self, node):
|
|
# move node from its current freq bucket to freq+1 bucket head
|
|
old_list = self._freq[node.freq]
|
|
old_list.remove(node)
|
|
if old_list.is_empty():
|
|
del self._freq[node.freq]
|
|
if self._min_freq == node.freq:
|
|
self._min_freq += 1
|
|
node.freq += 1
|
|
self._freq.setdefault(node.freq, _DLList()).add_front(node)
|
|
|
|
def get(self, key):
|
|
if key not in self._key:
|
|
return -1
|
|
node = self._key[key]
|
|
self._touch(node)
|
|
return node.value
|
|
|
|
def put(self, key, value):
|
|
if self.capacity == 0:
|
|
return
|
|
if key in self._key:
|
|
node = self._key[key]
|
|
node.value = value
|
|
self._touch(node)
|
|
return
|
|
# eviction if needed
|
|
if len(self._key) >= self.capacity:
|
|
evict_list = self._freq.get(self._min_freq)
|
|
if evict_list is not None:
|
|
node = evict_list.pop_tail()
|
|
if node is not None:
|
|
del self._key[node.key]
|
|
if evict_list.is_empty():
|
|
del self._freq[self._min_freq]
|
|
# insert new node at freq 1
|
|
node = _Node(key, value)
|
|
self._key[key] = node
|
|
self._freq.setdefault(1, _DLList()).add_front(node)
|
|
self._min_freq = 1 |