Очередь на выселение LFU
Кэш на c страниц работает по правилу LFU. У каждой страницы в кэше есть счётчик — сколько раз её запросили с тех пор, как она попала в кэш в последний раз. Запросы приходят по одному:
- если страница в кэше — это попадание, её счётчик растёт на единицу;
- если нет и в кэше есть свободное место, страница кладётся туда со счётчиком 1;
- если нет и кэш полон, сначала выселяется страница с наименьшим счётчиком; если таких несколько — та, к которой дольше всех не обращались. Выселенная страница забывает свой счётчик: вернувшись, она снова начнёт с 1.
Посчитайте попадания и выведите очередь на выселение после последнего запроса: страницы кэша по возрастанию счётчика, а при равных счётчиках — начиная с той, к которой дольше всех не обращались. Два теста — настоящие запросы к веб-серверу Космического центра Кеннеди в июле 1995 года, страница — её номер.
Вход
В первой строке — c и число запросов n (1 ≤ c ≤ n ≤ 5·105). Во второй — n номеров страниц, целые от 0 до 106.
Выход
В первой строке — число попаданий. Во второй — страницы кэша в порядке очереди на выселение.
В первом примере страницы 2 и 3 по очереди выбивают друг друга, не успев набрать второй запрос, а страница 1 со счётчиком 2 держится. Потом счётчик 2 набирает и страница 3, и когда приходит 4, уходит 1: счётчики равны, а к 1 дольше не обращались. Вернувшись, 1 начинает со счётчика 1 и в конце стоит в очереди первой. Во втором примере у страниц 5, 6, 7 счётчики по 2, и первой уходит 5 — её спрашивали раньше всех; в конце 5 вернулась со счётчиком 1 и стоит в очереди первой.
Примеры
Пример 1
2 9 1 2 1 3 2 3 3 4 1
2 1 3
Пример 2
3 10 5 6 7 5 6 7 8 9 8 5
3 5 6 7
Ограничения
- Время · Python
- 10000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Найти страницу с наименьшим счётчиком перебором — O(c) на промах. При пятидесяти тысячах мест и сотнях тысяч промахов это миллиарды шагов. Что, если держать страницы сгруппированными по счётчику?
2Идея
Заведём корзины: в корзине f — страницы со счётчиком f, в порядке последнего обращения, от давней к свежей. Попадание переносит страницу из корзины f в конец корзины f + 1. Выселяется первая страница самой маленькой непустой корзины. Номер этой корзины легко поддерживать без поиска: новая страница всегда приходит со счётчиком 1, так что после промаха наименьший счётчик — 1; а когда попадание опустошает корзину с наименьшим счётчиком, наименьшим становится f + 1 — туда только что ушла страница.
3Разбор
Нужны словарь «страница → счётчик» и словарь «счётчик → корзина», где корзина — упорядоченное множество: в Python — словарь (он помнит порядок добавления, а первый ключ даёт next(iter(d))), в Go — двусвязный список и словарь «страница → её узел». Все операции — найти страницу, вынуть из корзины, добавить в конец, вынуть первую — стоят O(1).
Очередь в конце — корзины по возрастанию счётчика, а внутри корзины — от давних к свежим. На дне 13 июля кэш на сто страниц ловит 103 127 запросов из 128 932 — те 79,99 %, что в статье.
3+Решение
4Сложность
O(1) на запрос, O(n) на все. Сортировка корзин в конце — O(k log k) для k разных счётчиков, а их не больше, чем страниц в кэше.
5Типичные ошибки
- Помнить счётчик выселенных. Так устроен «полный» LFU, но здесь вернувшаяся страница начинает с единицы. На первом же примере ответы расходятся.
- Равные счётчики. Из нескольких страниц с наименьшим счётчиком уходит самая давняя по последнему обращению, а не по первому появлению в кэше: после попадания страница встаёт в конец новой корзины.
- Перебор при выселении. Пятый тест: пятьдесят тысяч мест и почти одни промахи.
Алгоритмы задачи
O(1) на запрос у обоих
2 задачи
DS
Структура данных
LRU-кэш
Словарь плюс двусвязный список: get и put за O(1), выселяется тот, к кому дольше всех не обращались.
O(1) на get и put
2 задачи