Что такое мемоизация и почему это важно?
Мемоизация — это метод программирования, который повышает производительность за счет кэширования возвращаемых значений дорогостоящих вызовов функций. «Запоминаемая» функция немедленно выводит предварительно вычисленное значение, если ей предоставлены входные данные, которые она видела раньше.
Мемоизация — это особая форма кэширования, которая подходит для сценариев, в которых дорогостоящая функция выполняется многократно, иногда с одними и теми же аргументами. При условии, что функция чистая, то есть она всегда выдает одно и то же значение из определенного набора входных данных, ее запоминание может повысить эффективность и сократить количество циклов ЦП впустую.
Мемоизация чаще всего встречается в функциональных языках программирования. Однако эта техника имеет широкое применение. Это абстрактная концепция, которую вы можете включить в любой рекурсивный код. В этой статье мы используем JavaScript, но вы можете переписать примеры на свой рабочий язык.
Простой пример
Вот простая функция, которая генерирует факториал заданного целого числа:
const factorial = n => {
if (n === 0) return 1;
else return (factorial(n - 1) * n);
};Вычисление факториала является рекурсивным, так как factorial() вызывает сам себя в условии else. Вычисление также чистое, так как любое заданное значение n всегда будет возвращать одно и то же значение. factorial(5) равно 120, независимо от состояния программы.
Из-за рекурсивного характера функции вычисление факториала нескольких больших чисел приводит к напрасным операциям:
const x = factorial(100); const y = factorial(50);
Все вычисления, необходимые для вычисления y, были уже выполнены как часть вычисления x. Если бы factorial() кэшировал свои входные данные и соответствующие им выходные данные, вычисление y можно было бы значительно ускорить.
Запоминание факториальной функции
Вот базовый подход, который запоминает функцию factorial():
const cache = {};
const factorial = n => {
if (cache[n]) {
return cache[n];
}
let value;
if (n === 0) value = 1;
else value = (factorial(n - 1) * n);
cache[n] = value;
return value;
};Теперь есть объект cache, который factorial() использует для записи своих выходных значений. Каждый раз, когда функция вызывается, она сначала проверяет, видела ли она ранее ввод n. Если это так, он может немедленно замкнуться и вернуть кэшированное значение. В противном случае рекурсивный расчет выполняется как обычно, но последующие запуски с использованием того же числа будут ускорены.
Теперь вычисление factorial(50) после factorial(100) будет намного эффективнее. Факториал 50 будет вычисляться как часть факториала 100, поэтому функция может возвращать значение почти мгновенно.
Более общее решение
Хотя приведенный выше код работает, он специфичен для функции factorial(). Если бы вы использовали другие подобные функции, вам нужно было бы вручную добавить код кэширования в каждую из них.
Более общее решение позволит вам обернуть любую функцию функцией более высокого порядка, которая обеспечивает возможность запоминания:
const memoize = fn => {
const cache = {};
return (...args) => {
const argsString = JSON.stringify(args);
if (!cache[argsString]) {
cache[argsString] = fn(...args);
}
return cache[argsString];
}
};Теперь вы можете настроить исходную функцию factorial():
const factorial = memoize(n => {
if (n === 0) return 1;
else return (factorial(n - 1) * n);
});Оборачивая factorial() в memoize(), он получает возможности автоматического запоминания. Функция-оболочка возвращает функцию new, которая перехватывает все вызовы factorial(), преобразует их аргументы в строку и проверяет, не встречались ли они ранее. Если они есть, предыдущее возвращаемое значение используется повторно без вызова реальной функции вообще. Когда появляются новые аргументы, функция вызывается, и ее вывод добавляется в кеш.
Оболочка использует синтаксис остальных параметров JavaScript, чтобы принимать переменное количество аргументов. Это означает, что он будет работать с любой функцией JavaScript. Этот подход использует JSON.stringify() для создания строкового представления аргументов, поэтому следует соблюдать осторожность, если вы вызываете функцию со сложными объектами, которые не могут быть полностью представлены в виде JSON. .
Когда не использовать мемоизацию?
Мемоизация может значительно повысить производительность, особенно при математически сложных операциях. Однако эту технику можно использовать не везде. Не все функции следует запоминать, так как в некоторых случаях это может привести к снижению производительности.
Оборачивая функцию в memoize(), вы заставляете сравнивать входные аргументы каждый раз, когда эта функция вызывается. Это само по себе потребует некоторого процессорного времени. Приведенный выше пример оболочки запускает JSON.stringify() каждый раз, когда вызывается функция, добавляя новые служебные данные.
Мемоизация подходит для функций, в которых высока вероятность того, что одни и те же входные значения будут встречаться регулярно. Если вы редко будете вызывать функцию с одними и теми же аргументами, попадание в кэш будет нечастым, и вы можете потерять производительность из-за сериализации и сравнения аргументов. Поддержка кеша также увеличивает использование памяти, так как все предыдущие входные и выходные данные должны быть сохранены.
Поэтому вам следует полностью оценить роль каждой функции в вашей программе, прежде чем принимать решение о запоминании. Сравните производительность с мемоизацией и без нее. Иногда бывает выгоднее полагаться на собственные оптимизации браузера.
Наконец, имейте в виду, что некоторые функции нельзя запомнить. Этот метод работает только с чистыми функциями — если ваша функция обращается к глобальным переменным или другому состоянию приложения, ее не следует запоминать!
const functionUsingGlobalState = n => {
if (n === window.scrollY) return true;
else return functionUsingGlobalState(n - 1);
}Запоминание приведенной выше функции может привести к неожиданным результатам после первого запуска. Значения n будут кэшироваться с использованием исходной версии window.scrollY. Оболочка мемоизации вернет кешированный вывод, даже если window.scrollY изменился.
Краткое содержание
Мемоизация — это форма кэширования, которая ускоряет выполнение повторяющихся рекурсивных операций. Это метод функционального программирования, который может быть реализован как универсальная оболочка для любой чистой функции.
Вы чаще всего будете сталкиваться с мемоизацией в часто вызываемых функциях, выполняющих сложные вычислительные операции. Это помогает избежать потерь, устраняя необходимость пересчитывать значения, которые уже были получены в ходе предыдущего вызова.
Преимущества мемоизации будут менее очевидны в функциях, которые просты для начала или вызываются нечасто. В некоторых случаях неправильное использование мемоизации может навредить производительности, поэтому не стоит слепо запоминать каждую функцию в вашем приложении.