В новом выпуске канала Machine Learning Street Talk ведущий Тим Скарф устроил необычный технический челлендж для своих гостей — ведущих ученых из Google DeepMind и Mila. В роли интервьюируемого выступил Петар Величкович (Petar Veličković), известный исследователь в области графовых нейронных сетей, который в прошлом был успешным участником олимпиад по программированию (ICPC) .
Задача заключалась в проектировании сложной системы кэширования, требующей не только базовых знаний алгоритмов, но и глубокого понимания структур данных для обеспечения оптимальной асимптотики.
🧠 Проблема кэширования: три уровня сложности 0:40
Тим Скарф предложил спроектировать класс Cache, способный хранить миллионы и даже миллиарды объектов (например, видео с YouTube) . Основное требование: метод get должен работать за константное время $O(1)$, а метод set — максимально быстро .
Каждый элемент в кэше характеризуется четырьмя параметрами:
- Key (ключ) — строка.
- Value (значение) — объект.
- Priority (приоритет) — число.
- Expiration (время истечения) — системное время .
Главная сложность заключается в правилах вытеснения (eviction) элементов при переполнении кэша:
- Правило А (Срок годности): Если есть элементы, время жизни которых истекло (expiration < текущего времени), нужно удалить один из них .
- Правило Б (Приоритет и LRU): Если истекших элементов нет, нужно удалить элемент с самым низким приоритетом. Если таких несколько — удаляется наименее востребованный из них (Least Recently Used, LRU) .
🛠 Построение архитектуры: от хэш-таблиц к кучам 6:02
Петар Величкович начал решение с обеспечения константного времени для метода get. Для этого необходима хэш-таблица (Hash Table), которая отображает ключи напрямую на значения (или ссылки на узлы в других структурах) .
Для реализации Правила А (удаление истекших элементов) Величкович предложил использовать очередь с приоритетом (Priority Queue), реализованную на базе бинарной кучи (Binary Heap) .
- Ключом в этой куче выступает время истечения (expiration).
- При вызове
setсистема проверяет корень кучи. Если время в корне меньше текущего, элемент извлекается и удаляется из основной хэш-таблицы . - В случае совпадения времени истечения используется дополнительное сравнение по ключу для детерминированности .
Однако возникла проблема согласованности данных: если элемент удаляется по правилу приоритета, его нужно быстро найти и удалить и из кучи истечения срока. В стандартной куче удаление из середины занимает линейное время $O(n)$, что недопустимо .
⚖️ Балансировка и Red-Black Trees 18:02
Чтобы добиться логарифмической сложности $O(\log n)$ для удаления элементов из произвольного места, Петар предложил заменить бинарные кучи на сбалансированные бинарные деревья поиска (Balanced BST), такие как Красно-черные деревья (Red-Black Trees) .
Ведущие кратко обсудили принципы работы красно-черных деревьев:
- Они обеспечивают логарифмическую высоту дерева за счет операций вращения .
- Существуют строгие правила раскраски узлов (например, у красного узла не может быть красных детей, а листья всегда черные) .
- Петар признался, что, несмотря на знание теории, ему никогда не приходилось реализовывать красно-черное дерево «с нуля» на практике .
🔗 Финальный штрих: Интеграция LRU 20:32
Самым сложным этапом стала интеграция правила Least Recently Used (LRU) внутрь иерархии приоритетов. Величкович предложил структуру, где каждый узел в дереве приоритетов указывает не на один элемент, а на двусвязный список (Doubly Linked List) .
Механика работы:
- Все элементы с одинаковым приоритетом находятся в одном списке.
- При обращении к элементу через
get, он перемещается в «голову» своего списка (splice-операция), что занимает $O(1)$ . - Хэш-таблица при этом должна хранить прямые указатели на узлы в этих двусвязных списках, чтобы обновление позиции происходило мгновенно .
- При необходимости вытеснения по приоритету, система берет узел с минимальным приоритетом из BST и удаляет элемент из «хвоста» его списка .
🚀 Асимптотика и «олимпиадные» хитрости 24:40
Итоговая сложность метода set в предложенной архитектуре составила $O(\log n)$, где $n$ — количество элементов в кэше . Петар отметил, что если количество уникальных приоритетов фиксировано и невелико, можно использовать «корзины» (buckets) и свести сложность к $O(1)$ для операций с приоритетами .
Для еще более экстремальной оптимизации Величкович упомянул деревья ван Эмде Боаса (van Emde Boas trees или vEB-trees), которые позволяют выполнять операции за $O(\log \log n)$ . Однако такие структуры требуют, чтобы ключи были представлены в виде битовых строк ограниченной вселенной .
В завершение беседы Петар вспомнил, что подобную задачу на проектирование LRU-кэша ему давали на реальном собеседовании в Google в 2015 году . Тим Скарф в шутку резюмировал, что с таким решением он бы точно нанял Петара на работу .
