Я знаю, что способ реализации этого кеша, возможно, не самый лучший, но я искренне не могу понять, почему это не работает. Я попробовал пройтись по своему коду и, насколько я понимаю, он должен работать. Кажется, проблема заключается в функции вставки, где узел помещается в начало DLL (между self.left, который всегда будет указывать на узел LFU) и между предыдущим узлом LFU.
Например, после добавив операторы печати, я увидел, что после 1 нажатия DLL выглядела как 0 1 0 (ожидалось). Но после нажатия 2 это выглядит как 0 2 0 (ожидается, что это будет 0 2 1 0. Извините, если это плохой вопрос или действительно простая проблема, я просто не могу разобраться даже после попытки использовать ChatGPT.
Это мой код:
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.reads = 1
self.next = None
self.prev = None
class LFUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.left, self.right = Node(0,0), Node(0,0)
self.left.next = self.right
self.right.prev = self.left
def remove(self, node):
# only happens at beginning (self.left.next)
prev, nxt = self.left, node.next
prev.next = nxt
nxt.prev = prev
def insert(self, node):
prev, nxt = self.left, self.left.next
node.prev = prev
node.next = nxt
nxt.prev = node
self.left.next = node
def swapNodes(self, node1, node2):
node1Prev = node1.prev
node2Next = node2.next
# make node1Prev.next = node2
node1Prev.next = node2
# make node2.prev = node1.prev and make node2.next = node1
node2.prev = node1Prev
node2.next = node1
# make node1.next = node2.next, make node1.prev = node2
node1.next = node2Next
node1.prev = node2
# make node2Next.prev = node1
node2Next.prev = node1
def get(self, key: int) -> int:
if key in self.cache:
self.cache[key].reads += 1
if self.cache[key].next != self.right and self.cache[key].reads > self.cache[key].next.reads:
self.swapNodes(self.cache[key], self.cache[key].next)
return self.cache[key].value
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache[key].reads += 1
self.cache[key].value = value
if self.cache[key].reads > self.cache[key].next.reads and self.cache[key].next != self.right:
self.swapNodes(self.cache[key], self.cache[key].next)
else:
node = Node(key,value)
self.cache[key] = node
if len(self.cache) == self.cap:
lru = self.left.next
self.remove(lru)
del self.cache[lru.key]
self.insert(node)
# print(f"{self.left.next.value},{self.right.prev.value}")
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Подробнее здесь: https://stackoverflow.com/questions/790 ... -inserting
