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

Задача

Повторить ARC

кэширование хеш-таблица связный список симуляция в проде

Кэш на c страниц работает по правилу ARC. Он держит четыре списка, в каждом страницы упорядочены от давней к свежей: в кэше лежат страницы списков T1 (их спросили один раз с тех пор, как они попали в кэш) и T2 (не меньше двух раз), а списки B1 и B2 — «призраки»: номера страниц, недавно выселенных из T1 и T2 соответственно, без самих страниц. Целое число p — сколько мест кэш хотел бы отдать под T1; вначале все списки пусты и p = 0.

Вспомогательное действие ВЫСЕЛИТЬ(x): если T1 не пуст и (|T1| > p или (x лежит в B2 и |T1| = p)), самая давняя страница T1 переходит в конец B1; иначе самая давняя страница T2 переходит в конец B2.

Запрос страницы x:

  1. x в T1 или в T2 — попадание: x переходит в конец T2.
  2. x в B1: p ← min(c, p + max(⌊|B2| / |B1|⌋, 1)); ВЫСЕЛИТЬ(x); x убирается из B1 и ставится в конец T2.
  3. x в B2: p ← max(0, p − max(⌊|B1| / |B2|⌋, 1)); ВЫСЕЛИТЬ(x); x убирается из B2 и ставится в конец T2.
  4. x нигде нет. Если |T1| + |B1| = c: при |T1| < c удаляется самый давний номер B1 и делается ВЫСЕЛИТЬ(x), а иначе самая давняя страница T1 просто удаляется. Если же |T1| + |B1| < c и |T1| + |T2| + |B1| + |B2| ≥ c: при сумме, равной 2c, удаляется самый давний номер B2, и в любом случае делается ВЫСЕЛИТЬ(x). После этого x ставится в конец T1.

Размеры в формулах — до изменений на этом шаге. Повторите работу кэша на последовательности запросов. Два теста — настоящие запросы к веб-серверу Космического центра Кеннеди в июле 1995 года.

Вход

В первой строке — c и число запросов n (1 ≤ c ≤ 104, 1 ≤ n ≤ 5·105). Во второй — n номеров страниц, целые от 0 до 106.

Выход

Шесть чисел: число попаданий, итоговое p и размеры T1, T2, B1, B2 после последнего запроса.

Во втором примере предпоследний запрос — страница 5, которая лежит в B2, когда |T1| = p = 1. По особому правилу ВЫСЕЛИТЬ место освобождает T1: страница 4 уходит в B1, а последний запрос, страница 1, попадает в T2.

Примеры

Пример 1

Вход
2 9
1 2 3 1 2 3 1 4 1
Выход
1 0 1 1 0 0

Пример 2

Вход
3 9
5 3 5 1 4 3 1 5 1
Выход
2 1 0 3 1 0

Ограничения

Время · Python
8000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Каждый шаг правил трогает списки только с краёв: вынуть самый давний, поставить в конец, убрать страницу из середины по её номеру. Какая структура делает всё это за O(1)?

2Идея

Каждый из четырёх списков — упорядоченное множество: двусвязный список плюс словарь «страница → её узел». В Python это OrderedDict: popitem(last=False) вынимает самый давний, move_to_end переносит в конец, del убирает по ключу. Тогда запрос стоит O(1), и вся работа — аккуратно перенести правила.

3Разбор

Порядок проверок важен: сначала T1 и T2 (попадание), потом B1 и B2 (призраки), потом «нигде нет». При попадании в призрака сначала меняется p, потом делается ВЫСЕЛИТЬ — и в нём проверка «x лежит в B2» видит x ещё в B2, — и только потом x убирается из призрака и ставится в конец T2. Деления целые, с нижней границей 1: даже при пустом противоположном списке p сдвигается хотя бы на единицу.

Что делают призраки. Если запрос попал в B1, значит, страницу, которую спросили один раз, выселили зря — кэшу стоит держать больше свежих страниц, и p растёт. Попадание в B2 — зря выселили частую, и p уменьшается. Шаг тем больше, чем меньше список, в который попали: редкое попадание в маленький список — сильный довод. На неделе журнала NASA в статье кэш на сто страниц держит p около семи: этот поток больше любит частоту, но совсем без мест для новичков, как LFU, он проигрывает.

3+Решение
4Сложность

O(1) на запрос, O(n) на все; память — O(c): в кэше и в призраках вместе не больше 2c номеров.

5Типичные ошибки
  • Особый случай ВЫСЕЛИТЬ. Если запрос пришёл из B2 и |T1| ровно p, место освобождает T1, а не T2. Без этого ответы расходятся уже во втором примере.
  • Порядок шагов при попадании в призрака. Если сначала убрать x из B2, особый случай не сработает; если сначала поставить x в T2, ВЫСЕЛИТЬ может выбросить его же.
  • Деление. Нужно целое деление и максимум с единицей; в вещественных числах получится другой p и другие ответы.

Алгоритмы задачи

SYS Алгоритм LFU и ARC Кэши, которые помнят частоту: LFU за O(1) на корзинах счётчиков и ARC, который сам делит места между свежими и частыми. O(1) на запрос у обоих 2 задачи DS Структура данных LRU-кэш Словарь плюс двусвязный список: get и put за O(1), выселяется тот, к кому дольше всех не обращались. O(1) на get и put 2 задачи
Каталог алгоритмов