Использование мемоизации в Python: простой пример и объяснение

Быстрый ответ

Мемоизация — это метод оптимизации, который ускоряет работу программ, сохраняя и впоследствии повторно используя результаты функций, вызванных с одинаковыми аргументами. Python поставляется со встроенными инструментами для мемоизации, например, декоратором, который посредством словаря сохраняет предыдущие результаты функций. Рассмотрим пример на примере вычисления чисел Фибоначчи:

def memoize(func):
    cache = {} # Это хранилище результатов
    def wrapper(n):
        if n not in cache:
            cache[n] = func(n)
        return cache[n]
    return wrapper

@memoize
def fib(n):
    return n if n <= 1 else fib(n-1) + fib(n-2)

print(fib(10)) # Быстрый расчет даже для крупных чисел 'n'

Применение декоратора @memoize модифицирует функцию fib(n), снижая количество её вызовов и улучшая скорость выполнения для любых 'n'.

Встроенная мемоизация с помощью functools

В Python предусмотрены встроенные декораторы для мемоизации, такие как @functools.cache и @functools.lru_cache, обеспечивающие базовые и расширенные возможности кэширования. Это избавляет от необходимости написания собственного кода мемоизации.

from functools import cache

@cache
def factorial(n):
    return n * factorial(n-1) if n else 1

print(factorial(5))  # После первого вызова результаты будут извлекаться из кэша

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

Если возникает необходимость гибкого управления процессом мемоизации, можно создать специфический для этого класс:

class Memoize:
    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        if args not in self.cache:
            self.cache[args] = self.func(*args)
        return self.cache[args]

@Memoize
def compute(*args):
    # Здесь происходит некое сложное вычисление
    pass

Визуализация

Мемоизация функционирует подобно невидимым помощникам, выполняющим рутинные задачи на заднем плане. Она преобразует функцию в эффективный инструмент, запоминающий предыдущие решения:

def find_treasure(room):
    if room in treasure_map:            # "Давайте проверю свои записи..."
        return treasure_map[room]       # "Вот это да! Найдено без труда!"
    treasure = solve_puzzle(room)       # "Интересная задачка, решим её..."
    treasure_map[room] = treasure       # "Нужно обязательно запомнить это."
    return treasure                         

treasure_map = {}  # Вот и наша карта сокровищ, созданная благодаря мемоизации!

Выживание в диких условиях с помощью мемоизации

Работа с изменяемыми типами данных

Мемоизация может вызвать проблемы с изменяемыми типами данных. Инструмент functools.wraps отлично подходит для сохранения метаданных функций при мемоизации:

from functools import wraps

def memoize(func):
    cache = {}
    @wraps(func)
    def wrapper(*args):
        key = tuple([str(arg) for arg in args])
        if key not in cache:
            cache[key] = func(*args)
        return cache[key]
    return wrapper

Параллелизм и мемоизация

В контексте параллельных вычислений мемоизация может создать сложности. Чтобы предотвратить конфликты доступа к ресурсам, используйте потокобезопасные структуры данных или механизмы синхронизации.

from functools import lru_cache
import threading

lock = threading.Lock()

@lru_cache(maxsize=None)
def thread_safe_func(*args):
    with lock:  # "Закрываю дверь на замок во время выполнения. Ваши услуги не требуются!"
        # Здесь выполняем потокобезопасную операцию
        pass

Сохранение результатов вне рамок времени выполнения

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

import shelve

def persistent_memoize(func):
    with shelve.open('memoize.db') as db:  # Нащ "внешняя память" для мемоизации
        def wrapper(*args):
            if args in db:
                return db[args]
            result = func(*args)
            db[args] = result
            return result
    return wrapper

Но помните: мемоизация не всегда является решением

• Для функций с побочными эффектами или зависящих от изменяющегося внешнего состояния
• Когда входные данные уникальны и маловероятно будут использоваться повторно
• Если затраты на хранение кэша перевешивают возможные преимущества из-за объема данных

Полезные материалы

1. functools — Higher-order functions and operations on callable objects — Python 3.12.1 documentation
2. Python Decorators: A Step-By-Step Introduction – dbader.org
3. Memoization – Wikipedia
4. 7. Memoization and Decorators | Advanced | python-course.eu
5. Memoization using decorators in Python – GeeksforGeeks
6. Medium