Вступление: Проблема «забывчивого» компьютера

Проблема большинства программ не в том, что процессор медленно считает, а в том, что он делает одну и ту же работу тысячи раз подряд.

По умолчанию компьютер «забывчив». Когда вы вызываете функцию, она каждый раз начинает выполнение с чистого листа. Ей всё равно, что миллисекунду назад вы уже передавали ей эти же самые аргументы и она уже находила ответ — она будет честно пересчитывать его заново, тратя ресурсы процессора и ваше время.

Почему функции работают долго?

Обычно это происходит по трем причинам:

  1. Сложные математические расчеты (обработка графики, криптография).

  2. Работа с внешними данными (запросы к API или тяжелые запросы к базе данных).

  3. Рекурсия — когда функция вызывает саму себя.

Пример: бесполезная работа

Самый наглядный пример — вычисление чисел Фибоначчи через рекурсию. Чтобы функция нашла 40-е число, ей нужно сначала найти 39-е и 38-е. Но чтобы найти 39-е, ей снова нужно найти 38-е (которое она только что искала для основного вызова) и 37-е.

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

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

Что такое мемоизация?

Если максимально коротко: мемоизация — это кэширование результатов функции.

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

Суть процесса

  1. Функция получает аргументы (например, x=5).

  2. Программа проверяет: «Считали ли мы уже это для x=5?»

  3. Если да — мгновенно возвращает сохраненный результат.

  4. Если нет — выполняет расчет, сохраняет его в память и выдает ответ.

Аналогия: Таблица умножения vs Вычисления в столбик

Представьте, что вам нужно умножить 12 \times 12.

  • Без мемоизации (вычисление в столбик): Вы каждый раз берете листок, множите 2 на 2, потом 2 на 1, складываете результаты... Вы делаете честную работу, тратите 10–20 секунд. Если я попрошу вас сделать это 100 раз подряд, вы 100 раз будете писать в столбик. Это и есть работа обычной функции.

  • С мемоизацией (таблица умножения): Вы один раз в жизни вычислили, что 12 \times 12 = 144, и зазубрили это. Теперь, когда вы слышите эти числа, ваш мозг не считает — он делает lookup (поиск) в памяти. Это срабатывает мгновенно.

Итог: Мы меняем процессорное время (вычисления) на оперативную память (хранение таблицы ответов). В современном программировании память стоит дешево, а время пользователя — дорого, поэтому такая сделка почти всегда выгодна.

Как это работает «под капотом»

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

Алгоритм «Спросил — Посчитал — Записал — Отдал»:

  1. Спросил: Функция получает входные данные (аргументы). Она первым делом лезет в кэш и проверяет: «Есть ли у меня ключ, соответствующий этим аргументам?»

  2. Посчитал: Если ключа нет (промах кэша), функция выполняет свой основной код — те самые тяжелые вычисления, ради которых всё затевалось.

  3. Записал: Полученный результат не просто возвращается пользователю, а сохраняется в кэш вместе с аргументами.

  4. Отдал: Теперь, когда результат в памяти, функция его возвращает. При следующем вызове с теми же данными всё закончится на первом пункте.

Роль словаря (dict)

В Python идеальным инструментом для этого является словарь. Почему именно он?

  • Скорость: Поиск по ключу в словаре (хеш-таблице) происходит почти мгновенно (O(1)), независимо от того, лежит там 10 значений или 10 миллионов.

  • Структура: Аргументы функции становятся ключами, а результат вычислений — значениями.

Важный нюанс: Чтобы это работало, аргументы функции должны быть хэшируемыми (неизменяемыми). Вы не сможете использовать список (list) как ключ кэша, потому что он может измениться. Обычно используют числа, строки или кортежи (tuple).

Как это выглядит в логике кода:

cache = {}

def heavy_task(n):
    # 1. Спросил
    if n in cache:
        return cache[n]
    
    # 2. Посчитал
    result = n * n # Представим, что это очень долго
    
    # 3. Записал
    cache[n] = result
    
    # 4. Отдал
    return result

Вся «магия» под капотом — это банальная проверка наличия ключа в dict перед тем, как нагружать процессор.

Пишем мемоизацию вручную

Чтобы понять, как это работает, сначала напишем «плохой» код, а потом добавим в него память.

1. До: Обычная рекурсия (Медленно)

Эта функция вычисляет числа Фибоначчи. Она чистая и красивая, но абсолютно бесполезная для больших чисел.

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

# Попробуйте запустить это для n=40
print(fib(40))

Почему это тормозит: Для fib(40) функция сделает более 100 миллионов вызовов. Она будет бесконечно пересчитывать одни и те же значения, потому что каждый вызов «забывает» результат предыдущего.

2. После: Ручная мемоизация (Быстро)

Добавим словарь memo, который будет хранить уже вычисленные значения.

# Наш кэш (блокнот)
memo = {}

def fib_memo(n):
    # 1. Сначала проверяем, есть ли ответ в кэше
    if n in memo:
        return memo[n]
    
    # Базовые случаи
    if n <= 1:
        return n
    
    # 2. Считаем и ЗАПИСЫВАЕМ результат в кэш
    memo[n] = fib_memo(n-1) + fib_memo(n-2)
    
    return memo[n]

print(fib_memo(40))

Сравнение скорости

Если замерить время выполнения на среднем ноутбуке для n=35:

Версия

Время выполнения

Количество операций

Обычная рекурсия

~2–5 секунд

Миллионы

С мемоизацией

~0.00001 сек

35–40

Итог: Для n=40 обычная функция может заставить вас ждать минуту, а версия с мемоизацией выдаст ответ мгновенно. Мы просто перестали делать лишнюю работу, превратив экспоненциальный рост сложности в линейный. Теперь программа считает каждое число в ряду ровно один раз.

Профессиональный подход: Декоратор @lru_cache

В реальных проектах никто не создает словари руками для кэширования. В Python это считается «изобретением велосипеда», потому что в стандартной библиотеке уже есть готовый инструмент — модуль functools.

Как ускорить функцию одной строчкой

Самый простой способ внедрить мемоизацию — использовать декоратор @lru_cache. Вам нужно просто «навесить» его над вашей функцией.

from functools import lru_cache

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

Всё. Python сам создаст словарь, сам будет проверять наличие аргументов в нем и сам запишет результат. Ваша медленная рекурсивная функция мгновенно стала реактивной.

Что такое maxsize и зачем он нужен?

LRU расшифровывается как Least Recently Used (наименее недавно использованный). Это алгоритм управления памятью.

Параметр maxsize определяет, сколько результатов функция будет хранить в памяти:

  1. maxsize=None: Кэш неограничен. Функция будет помнить вообще всё. Это быстро, но если входных данных миллионы, программа может сожрать всю оперативную память.

  2. maxsize=128 (по умолчанию): Функция запомнит только 128 последних уникальных вызовов.

    • Как только лимит исчерпан, Python удалит самый старый результат, к которому давно не обращались, чтобы освободить место для нового.

Зачем это нужно в реальности?

Представь сервер, который обрабатывает запросы пользователей. Если ты поставишь maxsize=1000, сервер будет помнить ответы для тысячи самых активных пользователей. Как только придет 1001-й, сервер «забудет» того, кто заходил дольше всех. Это идеальный баланс между скоростью и экономией оперативной памяти.

Итог: Используй @lru_cache, когда хочешь мемоизацию «здесь и сейчас», не усложняя код лишними словарями. Это стандарт индустрии.

Когда мемоизация НЕ нужна (и даже вредна)

Мемоизация — это не «волшебная кнопка» для ускорения всего подряд. Если использовать её неправильно, вы получите либо сломанную логику, либо утечку памяти.

1. Функции с побочными эффектами

Мемоизация «пропускает» выполнение тела функции и просто отдает старый ответ. Если функция должна что-то сделать, а не только посчитать, кэш всё испортит.

  • Пример: Функция, которая отправляет письмо или печатает лог в консоль.

  • Что случится: Первый раз письмо уйдет и сообщение напечатается. При втором вызове с теми же данными Python просто вернет результат True, но письмо не отправится, и в консоли будет пусто. Тело функции просто не запустится.

2. Недетерминированные функции (зависимость от внешнего мира)

Кэшировать можно только те функции, которые для одного и того же x всегда возвращают один и тот же y.

  • Время: Если функция возвращает «текущее время», мемоизация заставит её вечно показывать время первого вызова.

  • API и Базы данных: Если вы кэшируете запрос к курсу валют, ваша программа будет показывать утренний курс даже вечером, когда всё изменилось.

  • Рандом: Функция get_random_bonus(user_id) всегда будет выдавать один и тот же «рандомный» бонус одному и тому же юзеру.

3. Проблема «раздувания» памяти

Кэш — это словарь, который живет в оперативной памяти.

  • Бесконечный рост: Если у функции миллионы возможных входных аргументов и вы используете @lru_cache(maxsize=None), ваш кэш будет бесконечно расти, пока не съест всю память и программа не вылетит с ошибкой Out of Memory.

  • Тяжелые объекты: Если функция возвращает огромные списки или объекты (например, загружает в память 1 ГБ данных из файла), кэширование пары десятков таких вызовов мгновенно забьет RAM.

4. Проблема методов классов (Self)

Если вы повесите @lru_cache на метод класса, возникнет скрытая проблема:

class Worker:
    @lru_cache
    def heavy_method(self, n):
        ...

Кэш будет хранить ссылку на self (объект класса). Из-за этого сборщик мусора Python не сможет удалить объект из памяти, даже если он вам больше не нужен. Это классическая причина «утечек памяти» в Python-приложениях.

Итог: когда НЕ использовать

  1. Если функция меняет внешнее состояние (файлы, БД, экран).

  2. Если результат функции зависит от внешних факторов (время, погода, случайность).

  3. Если входных данных слишком много, а память ограничена.

  4. С методами классов (лучше использовать cached_property или ручное управление).

Заключение

Мемоизация — это самый простой способ оптимизации кода «малой кровью». Вам не нужно переписывать алгоритм или менять архитектуру, достаточно просто дать функции память. Главное — помнить, что вы меняете память на время: программа станет потреблять больше RAM, но перестанет нагружать процессор бесполезными повторами.

Чтобы понять, стоит ли внедрять мемоизацию в конкретном случае, сверьтесь с этим чек-листом.

Чек-лист: когда использовать мемоизацию

Если вы ответили «Да» на все 5 пунктов — мемоизация вам необходима:

  1. Функция «чистая»? (Для одних и тех же входных данных она ВСЕГДА возвращает один и тот же результат).

  2. Функция тяжелая? (Она делает сложные расчеты, парсит большие объемы данных или совершает рекурсивные вызовы).

  3. Аргументы часто повторяются? (Вызываете функцию с одними и теми же параметрами многократно в течение одного сеанса работы).

  4. Аргументы хэшируемые? (На вход подаются строки, числа или кортежи, а не списки или другие изменяемые объекты).

  5. Памяти достаточно? (Результаты работы функции не весят по гигабайту каждый, и их хранение не уронит сервер).

Анонсы новых статей, полезные материалы, а так же если в процессе у вас возникнут сложности, обсудить их или задать вопрос по этой статье можно в моём Telegram-сообществе. Смело заходите, если что-то пойдет не так, — постараемся разобраться вместе.

Вердикт:

  • Если это математика или сложная обработка текста — используйте.

  • Если это работа с сетью, временем или рандомом — забудьте.