LRU-кэш в одну строчку

Кэш нужен, чтобы запоминать результаты каких-то тяжелых операций: вычислений, доступа к диску или запросов в сеть. В Python есть отличный декоратор, чтобы элегантно снабдить вашу функцию кэшированием: @functools.lru_cache(maxsize=128, typed=False)

LRU значит least recently used. Кэшу задают максимальный размер, и при его достижении элементы начинают вытесняться. Первыми вытесняются элементы, неиспользованные дольше всех, а свободные места занимают свежие элементы.

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

from functools import lru_cache
import time

@lru_cache(maxsize=4)
def slow_sqr(i):
    print(f'Calculating sqr for {i}...')
    time.sleep(0.5)  # задумаемся...
    return i ** 2

for i in [1, 2, 3, 1, 3, 4, 4, 1]:
    print(f'i = {i}  => i ** 2 = {slow_sqr(i)}')

print(slow_sqr.cache_info())
# CacheInfo(hits=4, misses=4, maxsize=4, currsize=4)

📎 Пример. Можно не задавать ограничение размеру кэша. Вычислим числа Фибоначчи рекурсивным методом. Без @lru_cache этот метод экстремально неэффективный с ростом n. Однако, с кэшированием – это уже динамическое программирование и работает сравнительно быстро:

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

print(fib(500))

print(fib.cache_info())

• В основе кэша – словарь, поэтому все аргументы функции должны быть хэшируемы (hash). Надеюсь, никто не путает хэш (hash) и кэш (cache).

• Вызовы f(a=1, b=2) и f(b=2, a=1) – разные и создадут две записи в кэше.

• Рекомендуется ставить maxsize как степень двойки.

f.cache_info() – информация о размере кэша и статистике его работы

f.cache_clear() – очистка кэша

• Если аргумент декоратора typed=True, то аргументы разных типов будут кэшироваться отдельно. Пример: f(3) и f(3.0) будут отвечать разным записям в кэше.

Дополнение. С версии Python 3.8 можно применять lru_cache без аргументов (размер кэша по умолчанию 128 элементов):

@lru_cache
def f(x):
    ...

🤩 Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway! 👈

Добавить комментарий