Почему хеширование не удается в LRU Cacheing Проблема в Python - PullRequest
Новая
       19

Почему хеширование не удается в LRU Cacheing Проблема в Python

0 голосов
/ 13 февраля 2020

Недавно я наткнулся на пример онлайн для решения проблемы LRUCache для вопросов об интервью. Когда я скопировал код завершения в IDE и скомпилировал / запустил код, он выдавал KeyError во время выполнения тестового кода в главном разделе. 

class DLL:
   def __init__(self, key, value):
       self.key = key
       self.value = value
       self.next = None
       self.prev = None


class LRUCache:
   def __init__(self, capacity: int):
       self.head = DLL(-1, -1)
       self.tail = self.head
       self.tracker = {}
       self.capacity = capacity
       self.length = 0

   def get(self, key: int) -> int:
       if key not in self.tracker:
           return -1

       node = self.tracker[key]
       value = node.value

       while node.next:
           node.prev.next = node.next
           node.next.prev = node.prev
           self.tail.next = node
           node.prev = self.tail
           node.next = None
           self.tail = node

       return value

   def put(self, key: int, value: int) -> None:
       if key not in self.tracker:
           node = self.tracker[key]
           node.value = value
           while node.next:
               node.prev.next = node.next
               node.next.prev = node.prev
               self.tail.next = node
               node.prev = self.tail
               node.next = None
               self.tail = node

       else:
           node = DLL(key, value)
           self.tracker[hash] = node
           self.tail.next = node
           node.prev = self.tail
           self.tail = node
           self.length += 1
           if self.length > self.capacity:
               remove = self.head.next
               self.head.next = self.head.next.next
               self.head.next.prev = self.head
               del self.tracker[remove.key]
               self.length += 1

if __name__ == '__main__':
   lru = LRUCache(3)

   lru.put(1, 2)
   lru.put(2, 2)
   lru.put(3, 2)
   lru.get(3)
   lru.get(1)
   lru.put(4, 2)
   lru.get(4)

При появлении сообщения об ошибке: 

Traceback (most recent call last):
  File "LRUCache.py", line 63, in <module>
    lru.put(1, 2)
  File "LRUCache.py", line 36, in put
    node = self.tracker[key]
KeyError: 1

Проблема связана со строкой self.tracker[hash] = node, но я не могу понять, почему. Может кто-нибудь объяснить, что здесь происходит? В исходном сообщении нет секции комментариев, поэтому я застрял, пытаясь выяснить чужой код самостоятельно.

...