Задача 05H. lru_cache

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется реализовать на языке Python декоратор lru_cache. У функции должен быть следующий интерфейс:

from typing import Any, Callable, Hashable, Optional

HashableCallable = Callable[[Hashable, ...], Any]

def lru_cache(f: Optional[HashableCallable] = None, *, maxsize: int = 128) -> HashableCallable | Callable[[HashableCallable], HashableCallable]:
    '''Decorator to wrap a function with a memoizing callable that saves up to the `maxsize` most recent calls.

    Arguments:
        f: a function to decorate
        maxsize: maximal number of cached entries

    Returns:
        If `f` is None returns a shorthand decorator function with set `maxsize`.
        If `f` is not None return decorated function
    '''
    pass

В результате декорации функция должна кэшировать maxsize последних вызовов функции, где ключём являются переданные в функцию аргументы. То есть, при добавлении нового значения в кэш максимального размера из него будет удалена запись, которая была использована наиболее давно. Подробнее про LRU cache можно прочитать здесь. Гарантируется, что все передаваемые значения хэшируемы и могут быть использованы в качестве ключа словаря.

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

foo(1, 2) -> ((1, 2), ())
foo(1, b=2) -> ((1, ), (('b', 2), ))
foo(a=1, b=2) -> ((), (('a', 1), ('b', 2), ))

Возвращаемая в результате декорации функция должна также иметь следующие поля-функции.

import collections

CacheInfo = collections.namedtuple('CacheInfo', ['hits', 'misses', 'maxsize', 'currsize'])

def cache_info() -> CacheInfo:
    '''Returns information about cache state showing the following properties:

    hits: int, how many times decorated function result was pulled from cache
    misses: int, how many times decorated function was called
    maxsize: int, maximal cache size
    currsize: int, current cache size
    '''
    pass


def clear_cache():
    '''Clears cache'''
    pass


def cache_state() -> dict[tuple[tuple[Hashable, ...], tuple[tuple[str, Hashable], ...]], Any]:
    '''Returns current cache state: a dict-like object contatining
    mapping from function arguments specification to function result for these arguments.

    Arguments specification is a tuple with two elements:
        first element is a tuple containing positional arguments,
        second element is a tuple of tuples containing key, value pairs for keyword arguments passed to the function

    Arguments are saved in order they were passed to the function
    '''
    pass

Функция cache_info возвращает именованный tuple CodeInfo с полями

Функция clear_cache удаляет все элементы в кэше.

Функция cache_state возвращает словарь, отображающий текущее состояние кэша. Элементы словаря должны быть расположены в порядке "недавности" их использования.

Формат выходных данных

Код решения должен содержать только импортируемые модули, определение и реализацию функций.

Примеры тестов

Стандартный вход Стандартный выход
1 @lru_cache def fibonacci(n): match n: case 0: return 0 case 1: return 1 case _: return fibonacci(n - 2) + fibonacci(n - 1) print(fibonacci(256)) print(fibonacci.cache_info())
141693817714056513234709965875411919657707794958199867
CacheInto(hits=254, misses=257, maxsize=128, currsize=128)
2 @lru_cache(maxsize=2) def add(a, b): return a + b print(add(1, 2), add(3, 4), add(1, 2), add(5, 6)) print(add.cache_state())
3 7 3 11
{((5, 6), ()): 11, ((1, 2), ()): 3}

0.063s 0.009s 13