Декоратор кэширования Python: ограничение веса и вытеснение по FIFO

Кэш с учетом веса и вытеснением по FIFO

Модуль рендеринга графических текстур сохраняет сгенерированные буферы в оперативной памяти. Вместо привычного подсчёта количества записей система следит за суммарным бюджетом вычислительной сложности: для каждого набора параметров специальная функция вычисляет затраты в положительных целых условных единицах. Параметризованный декоратор мемоизации принимает предельный бюджет хранилища вместе с этой функцией оценки, удерживая баланс расходов в замыкании.

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

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

Что уже дано

В заготовке кода представлена функция-заглушка weighted_fifo_cache(budget, cost), которую необходимо реализовать. Вспомогательные классы и проверочные структуры данных доступны во время тестирования, реализовывать их заново не требуется.

Что нужно сделать

Реализуйте функцию weighted_fifo_cache(budget, cost), возвращающую декоратор для синхронных функций.

Параметры фабрики:

• budget — неотрицательное целое число от 0 до 1 000 000 (включая подклассы int), задающее предельный суммарный вес записей в кэше;
• cost — синхронная функция cost(*args, **kwargs), вычисляющая положительный целочисленный вес вызова от 1 до 2 000 000 (включая подклассы int) без возбуждения исключений.

Декорируемая функция принимает произвольные хэшируемые аргументы и возвращает любой объект (включая None, False, изменяемые коллекции и подклассы стандартных типов). Декоратор может применяться независимо к нескольким функциям (от 1 до 3) — каждая из них должна обладать собственным изолированным состоянием кэша, лимита и порядка FIFO.

Правила работы обёртки:

• Ключ кэша: формируется по соглашению (args, tuple(sorted(kwargs.items()))). Порядок передачи именованных аргументов не влияет на ключ. Нормализация значений по умолчанию или позиционных аргументов в именованные не требуется.
• Попадание в кэш (hit): возвращается сохранённый объект результата без вызова cost и без вызова декорируемой функции. Порядок FIFO при попадании не обновляется.
• Промах (miss):

1. Сначала вызывается функция cost(*args, **kwargs) с исходными аргументами.
2. Если вычисленный вес строго больше budget, результат вычисляется целевой функцией и сразу возвращается без сохранения в кэш и без вытеснения уже имеющихся записей.
3. Если вес не превышает budget, из кэша поочерёдно удаляются самые старые записи (в порядке их добавления), пока сумма оставшихся весов вместе с весом нового результата не станет меньше либо равна budget. Затем вызывается целевая функция, а её результат сохраняется в кэше вместе с его весом.

• Записи, чей вес в точности равен budget, допустимы для сохранения (при условии полного освобождения остального кэша).
• Возвращаемые объекты должны сохранять тождество (is), включая «ложные» значения (None, False, пустые коллекции).
• Обёртка обязана сохранять метаданные декорируемой функции: атрибуты из functools.WRAPPER_ASSIGNMENTS, сигнатуру интроспекции inspect.signature, пользовательские атрибуты и ссылку на исходную функцию в __wrapped__.

Ввод и вывод

Стандартные потоки ввода stdin и вывода stdout в решении не используются: считывать ввод и вызывать print() не нужно. После выполнения кода учащегося проверяющая система считывает из пространства имён модуля функцию верхнего уровня weighted_fifo_cache и вызывает её с проверочными аргументами.

Пример использования

calls = []
def cost(name):
    return len(name)
@weighted_fifo_cache(4, cost)
def render(name):
    calls.append(name)
    return name.upper()
print(render("aa"))
print(render("bb"))
print(render("aa"))
print(render("ccc"))
print(render("aa"))
print(calls)

Вывод:

AA
BB
AA
CCC
AA
['aa', 'bb', 'ccc', 'aa']