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

Кэш страниц

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

Веб-сервер держит в памяти последние нужные файлы, чтобы не читать их с диска. Памяти хватает на C файлов; когда приходит запрос к файлу, которого в памяти нет, а места не осталось, из памяти выбрасывается тот файл, к которому дольше всех не обращались, и на его место встаёт новый. Для каждого запроса нужно сказать, нашёлся ли файл в памяти.

Один из тестов — первые 30 000 успешных запросов к серверу Космического центра Кеннеди 13 июля 1995 года, в день старта «Дискавери», и память на 100 файлов.

Вход

В первой строке C и n (1 ≤ C ≤ 100 000, 1 ≤ n ≤ 200 000). Дальше n строк, в каждой — путь к файлу: непустая строка до 100 символов без пробелов. Вначале память пуста.

Выход

Одна строка из n символов: +, если файл нашёлся в памяти, и -, если нет.

Примеры

Пример 1

Вход

3 10
/
/logo.gif
/
/news.html
/clock.pl
/logo.gif
/
/clock.pl
/clock.pl
/news.html

Выход

--+----++-

Пример 2

Вход

1 5
a
a
b
a
a

Выход

-+--+

Ограничения

Время · Python: 6000 мс
Время · Go: 2000 мс
Память: 256 МБ
Проверка: 7 тестов

Разбор

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

1Подсказка 1

Список файлов в порядке последнего обращения отвечает на все вопросы: найденный файл переезжает в конец, а выбрасывается первый. Сколько стоит каждое из этих действий, если в памяти сто тысяч файлов?

2Подсказка 2

Найти файл по имени быстро умеет словарь. Вынуть элемент из середины и поставить в конец за O(1) умеет двусвязный список, если знать, где элемент лежит. Пусть словарь хранит именно это.

3Идея

LRU-кэш: словарь «путь → узел списка» и двусвязный список узлов в порядке обращений. Попадание: словарь находит узел, узел переезжает в начало списка. Промах при полной памяти: последний узел списка удаляется из списка и из словаря, новый узел встаёт в начало. Каждое действие — несколько указателей и одна операция словаря.

4Разбор

В Python готовая пара «словарь и двусвязный список» — collections.OrderedDict: move_to_end освежает файл, popitem(last=False) выбрасывает самый давний. Пути можно не превращать в строки: байтовые строки из sys.stdin.buffer годятся в ключи словаря как есть.

В Go — карта из пути в элемент container/list: MoveToFront при попадании, Remove(Back()) при выселении. Узел хранит путь, чтобы при выселении удалить его и из карты.

4+Решение

5Сложность

O(1) в среднем на запрос, O(n) всего; память — O(C). Список без словаря — O(C) на запрос: поиск по списку, удаление из середины и сдвиг при удалении первого элемента.

6Типичные ошибки

Обычный список. page in order, order.remove(page) и order.pop(0) — каждый O(C). На первом тесте незаметно, на четвёртом с памятью на сто тысяч файлов — двадцать миллиардов шагов.
Не освежать при попадании. Тогда получится FIFO, а не LRU: файл выбрасывается по времени появления, а не последнего обращения. В первом примере шестой и десятый запросы стали бы попаданиями — ответ --+--+-+++ вместо --+----++-.
Выселять до проверки попадания. Если память полна, а пришёл файл, который в ней есть, выбрасывать никого не нужно.
Круг на один файл длиннее памяти. В пятом тесте 50 001 файл запрашивается по кругу при памяти на 50 000: правильный ответ — ни одного попадания. Это не ошибка решения, а слабое место самого правила LRU.

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

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