Что такое мемоизация и как использовать её для оптимизации производительности?

Что такое мемоизация и как применять её для оптимизации?

• приём кеширования результатов функции
• сохраняет результаты для заданных входных аргументов
• при повторном вызове возвращает предварительно вычисленное значение
• уменьшает число повторных вычислений, особенно при рекурсии
• ускоряет работу ресурсоёмких функций pure
• эффективна для оптимизации чистых функций без побочных эффектов
• широко применяется в динамическом программировании и UI-рендерингах

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

Развёрнутый ответ

Основной ответ

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

Ключевые аспекты

• Идемпотентность функций: наибольшую эффективность мемоизация показывает для чистых функций, результат которых определяется только входными параметрами и которые не имеют побочных эффектов.
• Хранение состояния: как правило, для этого используется словарь или объект: комбинация аргументов выступает ключом, а вычисленный результат хранится в соответствующем значении.
• Trade-off — память vs скорость: хотя мемоизация сокращает длительность выполнения, она расходует дополнительную память. Поэтому размер кеша необходимо контролировать, в частности применяя LRU-стратегии.

Практический контекст

В React 18 мемоизацию часто используют для оптимизации ререндеров компоненты с помощью useMemo или useCallback — это помогает исключить лишние пересчёты и вызовы функций. В алгоритмах динамического программирования, например при вычислении чисел Фибоначчи, этот приём снижает экспоненциальную сложность до линейной. В backend сервисах мемоизация применяется для кэширования запросов к внешним API и результатов тяжёлых вычислений, благодаря чему растёт throughput, а latency уменьшается: примерно до ~50ms вместо секунд.