Кэширование результатов функции (memoization)

Кэширование результатов функции (Memoization)

Memoization — это техника оптимизации, которая сохраняет результаты вычислений функции и возвращает закэшированный результат при повторном вызове с теми же аргументами. Это критически важно для оптимизации рекурсивных функций, которые могут вычислять одно и то же много раз.

Базовый декоратор для memoization

Самое простое решение использует словарь для хранения результатов:

def memoize(func):
    cache = {}
    
    def wrapper(*args, **kwargs):
        # Создаём ключ из аргументов
        key = (args, tuple(sorted(kwargs.items())))
        
        if key in cache:
            return cache[key]
        
        result = func(*args, **kwargs)
        cache[key] = result
        return result
    
    return wrapper

@memoize
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(35))  # Выполнится за миллисекунды

Проблема: Если аргументы содержат изменяемые объекты (списки, словари), получим ошибку TypeError, так как они не хешируемы.

Улучшенный декоратор с поддержкой любых типов

import hashlib
import json
from functools import wraps

def memoize_advanced(func):
    cache = {}
    
    def make_key(*args, **kwargs):
        # Пытаемся преобразовать в JSON для сериализации
        try:
            key = json.dumps((args, kwargs), sort_keys=True, default=str)
            return hashlib.md5(key.encode()).hexdigest()
        except TypeError:
            # Fallback для объектов, которые нельзя сериализовать
            return str((args, kwargs))
    
    @wraps(func)
    def wrapper(*args, **kwargs):
        key = make_key(*args, **kwargs)
        
        if key not in cache:
            cache[key] = func(*args, **kwargs)
        
        return cache[key]
    
    # Добавляем методы для управления кэшем
    wrapper.cache_clear = lambda: cache.clear()
    wrapper.cache_info = lambda: {"size": len(cache), "cache": cache}
    
    return wrapper

@memoize_advanced
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

Использование встроенного functools.lru_cache

В Python уже есть встроенный декоратор, оптимизированный на C:

from functools import lru_cache

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

print(fibonacci(100))  # Очень быстро
print(fibonacci.cache_info())  # Узнаём информацию о кэше
print(fibonacci.cache_clear())  # Очищаем кэш

Параметры lru_cache:

• maxsize — максимальный размер кэша (по умолчанию 128)
• typed — если True, кэширует аргументы разных типов отдельно (3 и 3.0 — разные ключи)

LRU cache с поддержкой именованных параметров

from functools import lru_cache

@lru_cache(maxsize=256)
def expensive_computation(base, exponent=2, modulo=None):
    result = base ** exponent
    if modulo:
        result %= modulo
    return result

print(expensive_computation(2, 10))  # Кэшируется
print(expensive_computation(2, exponent=10))  # Другой ключ, не кэшируется
print(expensive_computation(base=2, exponent=10))  # То же самое

Декоратор с TTL (Time-To-Live)

Для ситуаций, когда кэш должен устаревать со временем:

import time
from functools import wraps

def memoize_with_ttl(ttl_seconds=60):
    def decorator(func):
        cache = {}
        timestamps = {}
        
        @wraps(func)
        def wrapper(*args, **kwargs):
            key = (args, tuple(sorted(kwargs.items())))
            current_time = time.time()
            
            # Проверяем, есть ли кэш и не устарел ли он
            if key in cache:
                if current_time - timestamps[key] < ttl_seconds:
                    return cache[key]
                else:
                    del cache[key]
                    del timestamps[key]
            
            result = func(*args, **kwargs)
            cache[key] = result
            timestamps[key] = current_time
            return result
        
        return wrapper
    return decorator

@memoize_with_ttl(ttl_seconds=30)
def get_api_data(user_id):
    # Имитация дорогого API запроса
    return f"Data for user {user_id}"

Сравнение методов

Практические применения

• Рекурсивные функции (Fibonacci, факториал, комбинаторика)
• Дорогостоящие вычисления (парсинг, обработка больших данных)
• API запросы (с TTL для актуальности данных)
• Динамическое программирование (экономия памяти)

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

❌ Забывают сделать аргументы хешируемыми — используй tuples вместо lists

❌ Кэшируют глобальное состояние — функция должна быть pure

❌ Забывают про side effects — не кэшируй функции с побочными эффектами