Fichas
LRU Cache
Fichas del conjunto (1)
- 1LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4 class Node: def __init__(self, key, value): self.key = key self.value = value self.prev = None self.next = None class LRUCache(object): def __init__(self, capacity): self.capacity = capacity self.head = Node(0,0) self.tail = Node(0,0) self.head.next = self.tail self.tail.prev = self.head self.dict = dict()def get(self, key):
if key in self.dict:
node = self.dict[key]
self._remove(node)
self._add(node)
return node.value
return -1
def put(self, key, value):
if key in self.dict:
self._remove(self.dict[key])
node = Node(key, value)
self._add(node)
self.dict[key] = node
if len(self.dict) > self.capacity:
node = self.head.next
self._remove(node)
del self.dict[node.key]
def _add(self, node):
prev = self.tail.prev
prev.next = node
node.prev = prev
node.next = self.tail
self.tail.prev = node
def _remove(self, node):
prev = node.prev
next = node.next
prev.next = next
next.prev = prev
Información
- Descripción
- Fichas sobre LRU Cache, creado por Suhas S el 01/06/2018.
- Creado por
- Suhas S
- Visitas
- 0
- Valoración