Ответ
Мемоизация — это техника оптимизации, при которой результаты выполнения "дорогих" функций сохраняются (кэшируются), чтобы избежать повторных вычислений с теми же входными аргументами.
В Python самый простой способ реализовать мемоизацию — использовать декоратор functools.lru_cache.
Использование lru_cache
Декоратор lru_cache (Least Recently Used) кэширует результаты вызовов функции. Если функция вызывается повторно с теми же аргументами, результат возвращается из кэша, а не вычисляется заново.
Пример:
import time
from functools import lru_cache
# maxsize - максимальное количество хранимых результатов
# Если maxsize=None, кэш будет неограниченным
@lru_cache(maxsize=128)
def fibonacci(n):
print(f"Вычисляем fibonacci({n})...")
if n < 2:
return n
return fibonacci(n-1) + fibonacci(n-2)
# Первый вызов - все значения будут вычислены
print("Первый вызов:")
start = time.time()
result = fibonacci(10)
print(f"Результат: {result}, время: {time.time() - start:.6f} сек")
# Второй вызов - результат будет взят из кэша мгновенно
print("nВторой вызов:")
start = time.time()
result = fibonacci(10)
print(f"Результат: {result}, время: {time.time() - start:.6f} сек")Важные аспекты и ограничения:
- Хешируемые аргументы: Все аргументы функции должны быть хешируемыми (числа, строки, кортежи, frozenset). Списки и словари использовать нельзя.
- Чистые функции:
lru_cacheлучше всего подходит для "чистых" функций, результат которых зависит только от входных аргументов и не имеет побочных эффектов. - Потокобезопасность: Кэш является потокобезопасным.
Когда lru_cache недостаточно?
lru_cache реализует in-memory кэш в рамках одного процесса. Для более сложных сценариев требуются другие решения:
- Распределенное кэширование: Если приложение работает в нескольких процессах или на нескольких серверах, необходим внешний кэш, такой как Redis или Memcached. Это позволяет всем экземплярам приложения использовать общий кэш.
- Персистентное кэширование: Если нужно, чтобы кэш сохранялся между перезапусками приложения, данные следует сохранять на диск, например, с помощью
joblib.Memoryили в базу данных.
Ответ 18+ 🔞
Давай разберём эту тему про мемоизацию, а то я вижу, у некоторых глаза уже стекленеют, как у пьяного ежа. Суть проще пареной репы, но с подвохами, конечно.
Представь, ты каждый день идёшь в булочную за одним и тем же батоном. Сначала ты спрашиваешь у продавщицы: «Мария Ивановна, почём батон?». Она тебе: «Тридцать рублей». На следующий день ты опять: «Мария Ивановна, почём батон?». Она, блядь, уже смотрит на тебя как на идиота: «Тридцать, Петрович, как вчера». А ты на третий день опять: «Мария Ивановна...». Вот чтобы не быть этим Петровичем, который каждый раз заново вычисляет цену батона, и придумали мемоизацию. Запомнил ответ на вопрос один раз — и всё, в следующий раз просто достал из кармана памяти.
В Питоне для этого есть готовый инструмент — functools.lru_cache. Это такой декоратор, который вешает на функцию волшебную табличку. Функция отработала с какими-то аргументами — результат записал в табличку. Позвали её с теми же аргументами снова — она даже не шелохнётся, а сразу плюнет тебе готовый ответ из этой таблицы.
Смотри, как это выглядит в деле. Возьмём классику — числа Фибоначчи. Без кэша это пиздец какой рекурсивный ад.
import time
from functools import lru_cache
# maxsize — это сколько последних результатов помнить.
# Поставил None — значит, помнить всё, как слон, до самого конца работы программы.
@lru_cache(maxsize=128)
def fibonacci(n):
print(f"Вычисляем fibonacci({n})...") # Это чтобы видеть, когда реально считаем
if n < 2:
return n
return fibonacci(n-1) + fibonacci(n-2)
# Первый заход. Тут будет дикая возня, функция сама себя будет вызывать до посинения.
print("Первый вызов:")
start = time.time()
result = fibonacci(10)
print(f"Результат: {result}, время: {time.time() - start:.6f} сек")
# Второй заход. А тут уже — красота! Все значения для 10 и меньше уже в кэше лежат.
print("nВторой вызов:")
start = time.time()
result = fibonacci(10)
print(f"Результат: {result}, время: {time.time() - start:.6f} сек")Запустишь — увидишь, что в первый раз print начнёт строчить, как сумасшедший, а во второй раз — тишина и мгновенный результат. Вот она, магия, ёпта!
Но не всё так гладко, есть подводные ебалы
- Аргументы должны быть хешируемыми. Это, блядь, самое важное! Кэш — это словарь, ключами в котором являются аргументы твоей функции. А ключ в словаре должен быть неизменяемым и хешируемым. Цифры, строки, кортежи — пожалуйста. А вот списки, словари или твой самописный объект без метода
__hash__— нихуя не получится. «TypeError: unhashable type: 'list'» — и сиди, расшифровывай. - Функция должна быть чистой. То есть её результат должен зависеть ТОЛЬКО от того, что ты ей скормил. Если внутри она читает текущее время, случайное число или состояние вселенной — кэшировать это бесполезно, а то и опасно. Получишь вчерашний результат на сегодняшний вопрос.
- Потокобезопасность. Тут
lru_cacheмолодцом — его можно в потоках юзать, не боясь, что кэш развалится в самый ответственный момент.
А когда lru_cache уже не катит?
Вот представь, твоё приложение размножилось и бегает на пяти серверах. На одном сервере ты посчитал сложную хуйню и закэшировал. А на другом сервере другой процесс про тот же самый результат понятия не имеет и начинает считать всё заново. Получается, ты экономишь ресурсы одного ядра, но в масштабах кластера нихуя не экономишь. Это как если бы в каждой квартире подъезда жил свой Петрович, и все они по отдельности ходили спрашивать про цену батона.
Для таких распиздяйских масштабов нужен внешний кэш: Redis или Memcached. Это такая отдельная, блядь, служба, к которой все твои серверы ходят как к единой Марии Ивановне за запомненными ответами.
Ну и если ты хочешь, чтобы кэш пережил перезагрузку твоего приложения (чтобы не вычислять заново то, что считалось три дня), то lru_cache тоже не помощник — он живёт только в оперативке. Тут надо смотреть в сторону персистентных штук вроде joblib.Memory или просто писать результаты в БД. Но это уже, как говорится, совсем другая история, и костылей там — овердохуища.