Кратко — выявленные ошибки и полная реализация.
Ошибки в исходном коде
- Неинициализирована структура хранения: `self.d` не создана.
- Нет ограничения по ёмкости: при добавлении не освобождается место.
- `get` не обновляет порядок использования (не помечает ключ как недавно использованный).
- `put` не обрабатывает замену значения для существующего ключа корректно с точки зрения порядка.
- Поведение при отсутствии ключа не определено (возникает `KeyError`).
- Отсутствуют требования по сложности; наивные структуры могут давать хуже, чем требуется.
Требование (желательное): операции `get` и `put` работают за постоянное время $\mathcal{O}(1)$.
Реализация (дешёвая и надёжная) — словарь + двусвязный список. Код:
class LRU:
class _Node:
__slots__ = ('key', 'val', 'prev', 'next')
def __init__(self, key=None, val=None):
self.key = key
self.val = val
self.prev = None
self.next = None
def __init__(self, n):
if n <= 0:
raise ValueError("capacity must be > 0")
self.capacity = n
self.map = {} # key -> node
# Dummy head and tail to avoid проверки на None
self.head = LRU._Node()
self.tail = LRU._Node()
self.head.next = self.tail
self.tail.prev = self.head
def _add_to_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
prev = node.prev
nxt = node.next
prev.next = nxt
nxt.prev = prev
def _move_to_head(self, node):
self._remove_node(node)
self._add_to_head(node)
def _pop_tail(self):
# возвращает узел, который удаляем (LRU)
node = self.tail.prev
if node is self.head:
return None
self._remove_node(node)
return node
def get(self, key):
node = self.map.get(key)
if not node:
return None # можно вернуть -1 или бросать исключение — по требованию
self._move_to_head(node)
return node.val
def put(self, key, value):
node = self.map.get(key)
if node:
node.val = value
self._move_to_head(node)
return
new_node = LRU._Node(key, value)
self.map[key] = new_node
self._add_to_head(new_node)
if len(self.map) > self.capacity:
tail = self._pop_tail()
if tail:
del self.map[tail.key]
Пояснения и сложности
- Храним указатели и словарь: вставка, удаление и сдвиг в двусвязном списке — константное время; доступ по ключу через словарь — также константное время. Следовательно, `get` и `put` — за $\mathcal{O}(1)$.
- Поведение при отсутствии ключа в `get` возвращает `None` (можно изменить на `-1` или бросать `KeyError` по договорённости).
- Валидация ёмкости при создании: `n` должен быть положительным.
Альтернатива (короче): использовать `collections.OrderedDict`:
from collections import OrderedDict
class LRU:
def __init__(self, n):
if n <= 0:
raise ValueError("capacity must be > 0")
self.cap = n
self.od = OrderedDict()
def get(self, k):
if k not in self.od:
return None
self.od.move_to_end(k, last=False)
return self.od[k]
def put(self, k, v):
if k in self.od:
self.od[k] = v
self.od.move_to_end(k, last=False)
return
self.od[k] = v
self.od.move_to_end(k, last=False)
if len(self.od) > self.cap:
self.od.popitem(last=True)
Эта реализация тоже обеспечивает `get`/`put` в среднем за $\mathcal{O}(1)$.