Проектирование LRU-кэша

LRU (Least Recently Used) кэш при переполнении вытесняет элемент, к которому дольше всего не обращались. Идея проста: недавно использованное с большой вероятностью понадобится снова. Практическое требование: и get(key), и put(key, value) должны работать за O(1). Про готовый кэш функций см. мемоизацию и lru_cache; здесь мы построим сам кэш.

Почему одной структуры мало

• dict находит по ключу за O(1), но не знает, какой элемент «самый старый».
• Список хранит порядок, но поиск ключа в нём O(n).

Решение: dict + двусвязный список (двусвязный список).

• dict: ключ → узел списка.
• Список: у головы «самый свежий», у хвоста «самый старый» элемент.
• get: находит узел и переносит в начало списка.
• put: ставит узел в начало, при превышении ёмкости удаляет узел у хвоста.

Список должен быть двусвязным: чтобы удалить узел из середины за O(1), нужен его указатель prev. Сторожевые узлы (head, tail) убирают граничные случаи: список никогда не встречает «пустой указатель» (идея dummy).

Реализация

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

class LRUCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev