Мемоизация в JS и ускорение функций

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

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

Функция вычисления факториала и кэширование

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

Например, вот функция factorial , которая вычисляет и возвращает факториал числа. Если не вдаваться в детали её реализации, выглядеть она будет так:

Вызовем её следующим образом: factorial(50) . Она, как и ожидается, найдёт и возвратит факториал числа 50. Всё это хорошо, но давайте теперь найдём с её помощью факториал числа 51. Компьютер снова выполнит вычисления, и то, что нам надо, будет найдено. Однако, можно заметить, что, при повторном вызове, функция выполняет массу вычислений, которые уже были выполнены ранее. Попытаемся функцию оптимизировать. Подумаем, как, имея значение factorial(50) перейти к factorial(51) без повторного вызова функции. Если следовать формуле вычисления факториала, окажется, что factorial(51) это то же самое, что и factorial(50) * 51 .

При подобном подходе, однако, выигрыша в производительности получить не удастся. А именно, сначала, внутри функции factorial() производится полная цепочка вычислений для нахождения факториала 50, а потом то, что получилось, умножается на 51. То есть, при использовании подобной функции, вычисление факториала для числа 51 в любом случае выглядит как перемножение всех чисел от 1 до 51.

Хорошо было бы, если бы функция factorial() умела запоминать результаты вычислений, выполненных при её предыдущих вызовах и использовать их при следующих вызовах для ускорения производительности.

Основы мемоизации

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

Вот как может выглядеть простая функция с мемоизацией. Этот код есть на CodePen, так что можете тут же с ним поэкспериментировать.

Анализ кода функции с мемоизацией

Проанализировав вышеприведённый фрагмент кода, можно сделать следующие выводы:

Функция memoizeAdd возвращает другую функцию, которую мы можем вызвать тогда, когда нужно. Такое возможно потому что функции в JavaScript — это объекты первого класса, что позволяет использовать их как функции высшего порядка и возвращать из них другие функции.

Написание функции с мемоизацией

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

Отлично! Наша функция memoize способна превращать другие функции в их эквиваленты с мемоизацией. Конечно, этот код не универсален, но его несложно переделать так, чтобы функция memoize могла бы работать с функциями, имеющими любое количество аргументов.

Подобное можно написать самостоятельно, но существуют и библиотечные решения:

В Lodash имеется функция _.memoize(func, [resolver])

Мемоизация рекурсивных функций

Если попытаться передать рекурсивную функцию рассмотренной выше функции memoize , или функции _.memoize из Lodash, то, что получится, будет работать неправильно, так как рекурсивные функции вызывают сами себя, а не то, что получается после добавления возможностей по мемоизации. Как результат, переменная cache в такой ситуации не выполняет своего назначения. Для того, чтобы решить эту проблему, рекурсивная функция должна вызывать свой вариант с мемоизацией. Вот как можно добавить мемоизацию в рекурсивную функцию вычисления факториала. Код, как обычно, можно найти на CodePen.

Проанализировав этот код, можно сделать следующие выводы:

• Функция factorial рекурсивно вызывает свою версию с мемоизацией.
• Функция с мемоизацией кэширует результаты вычисления факториала, что, при её последующих вызовах, значительно улучшает производительность. То есть, в вышеприведённом примере оказывается, что вместо перемножения чисел от 1 до 6 для нахождения факториала числа 6, на 6 придётся умножить лишь то, что было возвращено предыдущим вызовом factorial(5) .

О мемоизации и кэшировании

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

Итоги: когда стоит прибегать к мемоизации

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

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