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

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

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

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

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

  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-сообществе. Смело заходите, если что-то пойдет не так, — постараемся разобраться вместе.

Вердикт:

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

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