По мере того, как наши приложения растут и начинают выполнять более тяжелые вычисления, возникает все большая потребность в скорости и оптимизации. Если мы игнорируем эту проблему, то получаем программы, выполнение которых занимают много времени и потребляет чудовищное количество системных ресурсов.
Что такое мемоизация
Мемоизация — это метод оптимизации, который ускоряет приложения за счет сохранения результатов дорогостоящих вызовов функций и возвращения кешированного результата для одних и тех же входных данных.
Если это вам пока еще не очень понятно, не переживайте. Сейчас разберемся, зачем нужна мемоизация, что это такое, как она может быть реализована и когда ее следует использовать.
Очевидно, что цель мемоизации — сокращение времени и количества ресурсов, потребляемых при исполнении «дорогостоящих вызовов функций».
Что такое дорогостоящий вызов функции? Речь, конечно, идет не о деньгах. В контексте компьютерных программ двумя основными ресурсами являются время и память. Таким образом, дорогостоящий вызов — это вызов функции, которая потребляет огромные количества этих двух ресурсов во время выполнения из-за сложных вычислений.
Однако, как и с деньгами, мы должны быть экономными. Поэтому мемоизация использует кеширование для хранения результатов наших вызовов для быстрого и легкого доступа в более позднее время.
Кеш — это просто временное хранилище данных.
Когда тяжелая функция вызывается в первый раз, результат ее работы для конкретных входных данных сохраняется в кеше. При каждом следующем вызове сначала проверяется кеш. И если в нем найдется нужный результат, то повторно вычисления не производятся.
Почему мемоизация важна?
Представьте, что вы в парке читаете увлекательную книгу с яркой и привлекательной обложкой. Прохожим очень нравится эта обложка, поэтому они постоянно останавливаются и спрашивают у вас, что это за книга и кто ее автор. После первого вопроса вы смотрите на обложку и зачитываете интересующемуся название и фамилию писателя. Прохожих все больше и всем интересно. А вы очень хороший человек, поэтому отвечаете каждому.
Но вы ведь не переворачиваете больше книгу и не читаете с обложки. Теперь вы отвечаете по памяти и это экономит время.
Мемоизация делает то же самое. В первый раз она делает необходимые вычисления и «запоминает» результат, сохраняя его в кеше. Если в будущем она получит те же самые входные данные, то не будет вычислять повторно, а просто возьмет ответ из памяти (кеша).
В теории все очень просто, давайте посмотрим, как это работает на практике.
Как работает мемоизация?
Идея мемоизации в JavaScript основывается на двух концепциях:
- замыканиях
- и функциях высшего порядка — функциях, которые возвращают другие функции.
Замыкания
Замыкание — это комбинация функции и ее лексического окружения (окружения, в котором эта функция была объявлена).
Если вы испытываете сложности с пониманием замыканий, загляните сюда:
- Пора понять замыкания в JavaScript! Часть 1. Готовим фундамент
- Пора понять замыкания в JavaScript! Часть 2. Переходим к делу
Давайте быстро вспомним, что такое лексическое окружение в JS. Это просто ссылка на физическое положение переменных в момент написания кода.
Вот популярный сниппет из книги «You Don’t Know JS»:
function foo(a) {
var b = a + 2;
function bar(c) {
console.log(a, b, c);
}
bar(b * 2);
}
foo(3); // 3, 5, 10Здесь три области видимости:
- глобальный скоуп, который содержит единственный индентификатор
foo; - скоуп функции
foo, в котором естьa,bиbar; - и скоуп функции
bar, содержащийc.
Функция bar имеет доступ к переменной a и b, потому что она вложена в функцию foo. Эти переменные будут доступны ей всегда, независимо от места вызова — это ее замыкание (closure).
Можно перефразировать эту концепцию в контексте наследственности. Человек всегда имеет доступ к наследственным чертам и может проявлять их, даже если находится за пределами окружения, в котором он родился.
Это важное свойство замыканий плавно подводит нас ко второй концепции:
Возврат функций из функций
Функции, которые работают с другими функциями, либо принимая их в качестве аргументов, либо возвращая их, называются функциями высшего порядка (higher-order functions).
Замыкания позволяют нам вызывать внутреннюю функцию вне ее родительской функции, сохраняя при этом доступ к лексической области видимости родителя.
function foo(){
var a = 2;
function bar() {
console.log(a);
}
return bar;
}
var baz = foo();
baz();//2Обратите внимание, как функция foo возвращает функцию bar. Именно ссылка на bar оказывается в переменной baz после выполнения функции foo. А bar по-прежнему имеет доступ к своему замыканию, например, к идентификатору a.
В последней строчке кода мы выполняем функцию baz за пределами лексической области foo. Казалось бы, в этом месте она никак не может получить доступ к переменной a, чтобы вывести ее в консоль. Но ей это удается благодаря замыканию.
Теперь давайте посмотрим, как мемоизация использует эти концепции.
Последовательность Фибоначчи
Ряд Фибоначчи — это последовательность числе, начинающаяся с нуля или единицы, в которой каждое следующее число является суммой двух предыдущих.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
// или
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …Задача: написать функцию, которая возвращает n-ный член последовательности Фибоначчи.
Это типичная задача с рекурсивным решением.
function fibonacci(n) {
if (n <= 1) {
return 1
}
return fibonacci(n - 1) + fibonacci(n - 2);
}Короткий и аккуратный алгоритм, однако, есть проблема. Мы делаем очень много повторяющейся работы, постоянно вычисляем одни и те же значения. Например, при вызове функции для вычисления пятого члена последовательности, мы целых три раза вычислим ее второй член.
Эти избыточные вычисления и должна устранить мемоизация.
function fibonacci(n,memo) {
memo = memo || {}
if (memo[n]) {
return memo[n]
}
if (n <= 1) {
return 1
}
return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
}В приведенном выше фрагменте кода мы добавляем необязательный параметр функции — memo, который будем использовать в качестве кеша для хранения чисел Фибоначчи с их индексами в качестве ключа.
memo = memo || {}Здесь мы проверяем, был ли получен аргумент memo при вызове функции. Если нет, значит, это первый вызов — берем в качестве кеша пустой объект.
if (memo[n]) {
return memo[n]
}Теперь мы проверяем, есть ли кешированное значение для текущего ключа n, и возвращаем его, если есть.
Как и в предыдущем решении, мы указываем конечный случай, когда n меньше или равно 1.
В конце мы рекурсивно вызываем функцию с уменьшенным значением n, передавая ей кеш.
Обратите внимание, что мы добавляем конечный результат в кеш перед его возвращением.
Проверка производительности с JSPerf
По этой ссылке вы можете перейти на тест производительности нашей функции. Запустите его.
Ничего себе! Это реально впечатляет!
Функция, использующая мемоизацию оказалась намного быстрее. Она выполняет 126 762 ops/sec, что намного больше, чем чисто рекурсивное решение, которое выполняет 1,751 ops/sec и примерно на 99% медленнее.
Примечание: «ops/sec» означает операции в секунду. То есть, сколько раз в секунду выполняется тест.
Мемоизация может здорово повлиять на производительность приложения. Означает ли это, что придется переписать каждую дорогостоящую функцию с использованием кеша результатов?
Совсем нет. Помните, что возвращая одну функцию из другой, мы заставляем ее наследовать область видимости родителя? Таким образом можно передать функции и свойства. Давайте используем это знание, чтобы написать собственный мемоизатор.
Функциональный подход
Создадим функцию высшего порядка memoizer, которая позволит нам использовать мемоизацию для любой другой функции, не изменяя ее код.
function memoizer(fun){
let cache = {}
return function (n){
if (cache[n] != undefined ) {
return cache[n]
} else {
let result = fun(n)
cache[n] = result
return result
}
}
}Мы просто создаем новую функцию под названием memoizer, которая принимает любую функцию fun в качестве параметра. Внутри функции мы создаем объект кеша для хранения результатов выполнения этой функции.
Из функции memoizer возвращается новая функция, которая может обращаться к кешу независимо от того, где она выполняется (замыкание). В ней мы проверяем, существует ли кешированное значение для полученных входных данных. Если нет, вычисляем его и сохраняем в кеше. Если есть, возвращаем непосредственно из кеша.
Очень удобно! Теперь используем этот мемоизатор для рекурсивной функции Фибоначчи.
const fibonacciMemoFunction = memoizer(fibonacciRecursive)Тестирование мемоизатора
Результат тестирования поразителен!
42,982,762 ops/sec! Потрясающая оптимизация.
Итак, мы разобрались, что такое мемоизация, зачем она нужна и как работает. Теперь давайте посмотрим, когда она необходима.
Когда нужна мемоизация?
У вас может возникнуть соблазн мемоизировать все функции без разбора, однако это может оказаться очень непродуктивным. Вот три случая, в которых мемоизация реально полезна:
- Для дорогостоящих функций, т. е. функций, которые выполняют тяжелые вычисления.
- Для функций с ограниченным и повторяющимся диапазоном входных данных. При этом все возможные значения очень быстро попадают в кэш и функция вообще перестает работать.
- Для рекурсивных функций с повторяющимися входными значениями.
- Для чистых функций, т. е. функций, которые возвращают один и тот же результат для одних и тех же входных данных
Вот и все! Теперь вы вполне можете использовать мемоизацию в своих проектах.
1 комментарий