Содержание

Вариант 5.14. Кеш предварительно сформированных превью

Все варианты на «Отлично» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты

Уровень: Отлично.

Постановка задачи

key — идентификатор ресурса, value — токен уже сформированного превью. Создавать изображения не нужно; нужно хранить результаты до вытеснения или истечения.

Разработайте ограниченный по ёмкости кеш с истечением срока хранения. При нехватке места удаляется запись, к которой дольше всего не обращались. Независимо от этого запись удаляется при наступлении её срока истечения.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

Операции

Команда Действие Ответ
INIT capacity Очистить кеш, установить ёмкость и время 0; повторная инициализация разрешена. OK
PUT key value ttl Добавить/обновить запись, назначив срок expires=t+ttl, и считать её самой недавно использованной. OK
GET key Прочитать живую запись и считать её самой недавно использованной. VALUE value; при отсутствии NONE
PEEK key Прочитать запись без изменения порядка использования. VALUE value; при отсутствии NONE
DEL key Удалить запись. OK; при отсутствии Error: NOT_FOUND
TICK time Установить время и удалить все записи с expires ≤ time. Уменьшать время нельзя. OK; если time < t, Error: RANGE
RESIZE capacity Изменить ёмкость и вытеснить лишние записи от самых давно использованных. OK
LIST Получить все живые записи от недавно к давно использованным. ITEMS n, затем n строк key value expires

Правила выполнения и ошибки

До INIT все команды, кроме INIT, после проверки синтаксиса и статических диапазонов возвращают STATE. Истечение при точном равенстве уже удаляет запись. Поскольку время меняется только TICK, перед остальными командами не требуется обращаться к часам ОС.

PUT существующего ключа заменяет значение и срок, не увеличивая число записей. Успешные GET и PUT делают запись первой по недавности, неуспешный GET порядок не меняет. GET/PEEK не продлевают TTL. PEEK/LIST не меняют порядок. PUT нового ключа при заполнении вытесняет самую давно использованную запись. RESIZE сохраняет наиболее недавно использованные записи. Начальный/обновлённый срок может превышать 10^12 и вычисляется в int64. Для каждой живой записи сохраняется только один действующий срок; объём памяти не должен расти от повторных PUT одного ключа.

Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.

Требования к эффективности

GET/PEEK — ожидаемо O(L) либо гарантированно O(L·log(n+2)); PUT/DEL — не хуже O(L·log(n+2)). TICK — O(1+e·L·log(n+2)), где e — число истёкших записей; RESIZE — O(1+e·L·log(n+2)) для e вытеснений; LIST — O(nL). При отсутствии истёкших записей TICK не должен просматривать весь кеш. Память — O(capacity·L), включая все вспомогательные сведения, независимо от общего числа выполненных команд.

В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.

Формат ввода и вывода

Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:

Course work for option 5.14, created by Ivan Ivanov.

Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.

Примеры

Пример 1. Вытеснение и срок хранения

Ввод:

1
9
INIT 2
PUT a x 5
PUT b y 9
GET a
PUT c z 7
PEEK b
TICK 5
PEEK a
LIST

Вывод:

Course work for option 5.14, created by Ivan Ivanov.
OK
OK
OK
VALUE x
OK
NONE
OK
NONE
ITEMS 1
c z 7

Пример 2. Продление через PUT и точная граница

Ввод:

1
8
INIT 1
PUT a x 5
TICK 3
PUT a y 10
TICK 5
GET a
TICK 13
GET a

Вывод:

Course work for option 5.14, created by Ivan Ivanov.
OK
OK
OK
OK
OK
VALUE y
OK
NONE

Пример 3. Неудачная смена времени

Ввод:

1
7
INIT 2
PUT a x 10
TICK 4
TICK 3
PEEK a
DEL b
LIST

Вывод:

Course work for option 5.14, created by Ivan Ivanov.
OK
OK
OK
Error: RANGE
VALUE x
Error: NOT_FOUND
ITEMS 1
a x 10