Использование мемоизации в 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
Но помните: мемоизация не всегда является решением
- Для функций с побочными эффектами или зависящих от изменяющегося внешнего состояния
- Когда входные данные уникальны и маловероятно будут использоваться повторно
- Если затраты на хранение кэша перевешивают возможные преимущества из-за объема данных
Полезные материалы
- functools — Higher-order functions and operations on callable objects — Python 3.12.1 documentation
- Python Decorators: A Step-By-Step Introduction – dbader.org
- Memoization – Wikipedia
- 7. Memoization and Decorators | Advanced | python-course.eu
- Memoization using decorators in Python – GeeksforGeeks
- Medium