Задачник Базовый курс EN

Что решает

кэширование

Статьи

DS Структура данных Связный список Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов. O(1) у известного узла 2 задачи DS Структура данных Косое дерево После каждого запроса ключ поднимается в корень парами поворотов: частые ключи сами собираются наверху, амортизированно O(log n). O(log n) амортизированно на операцию; одна операция — до O(n) 1 задача DS Структура данных LRU-кэш Словарь плюс двусвязный список: get и put за O(1), выселяется тот, к кому дольше всех не обращались. O(1) на get и put 2 задачи SYS Алгоритм Консистентное хеширование Распределяет ключи по серверам так, что при добавлении сервера переезжает лишь его доля. O(log(N·v)) на поиск сервера 1 задача SYS Алгоритм Рандеву-хеширование Каждый ключ уходит к серверу с наибольшим хешем пары «ключ, сервер»: равномерно, без таблиц, отказ сдвигает только ключи упавшего. O(N) на ключ 2 задачи SYS Алгоритм LFU и ARC Кэши, которые помнят частоту: LFU за O(1) на корзинах счётчиков и ARC, который сам делит места между свежими и частыми. O(1) на запрос у обоих 2 задачи TEC Приём Мемоизация Запомнить ответ функции для каждого набора аргументов, чтобы не считать его заново: экспонента превращается в многочлен. O(число разных аргументов × работа на один вызов) 2 задачи

Задачи

Кэш страниц Новый сервер в кольце Очередь на выселение LFU Повторить ARC Цена журнала Кэш любого размера

Часто рядом

собеседования 6 в проде 4 связный список 3 операционные системы 3 классика 3 хеш-таблица 3 базы данных 3 балансировка 2 репликация 2 хеширование 2 распределённые системы 2 массив 1