Разбираемся с мемоизацией в JavaScript | В паутине

Разбираемся с мемоизацией в JavaScript

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

Что такое мемоизация

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

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

Очевидно, что цель мемоизации — сокращение времени и количества ресурсов, потребляемых при исполнении «дорогостоящих вызовы функций».

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

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

Кеш — это просто временное хранилище данных.

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

Почему мемоизация важна?

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

Но вы ведь не переворачиваете больше книгу и не читаете с обложки. Теперь вы отвечаете по памяти и это экономит время.

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

В теории все очень просто, давайте посмотрим, как это работает на практике.

Как работает мемоизация?

Идея мемоизации в JavaScript основывается на двух концепциях:

  • замыканиях
  • и функциях высшего порядка — функциях, которые возвращают другие функции.

Замыкания

Замыкание — это комбинация функции и ее лексического окружения (окружения, в котором эта функция была объявлена).

Если вы испытываете сложности с пониманием замыканий, загляните сюда:

Давайте быстро вспомним, что такое лексическое окружение в JS. Это просто ссылка на физическое положение переменных в момент написания кода.

Вот популярный сниппет из книги «You Don’t Know JS»:

Здесь три области видимости:

  • глобальный скоуп, который содержит единственный индентификатор foo;
  • скоуп функции foo, в котором есть a, b и bar;
  • и скоуп функции bar, содержащий c.

Функция bar имеет доступ к переменной a и b, потому что она вложена в функцию foo. Эти переменные будут доступны ей всегда, независимо от места вызова — это ее замыкание (closure).

Можно перефразировать эту концепцию в контексте наследственности. Человек всегда имеет доступ к наследственным чертам и может проявлять их, даже если находится за пределами окружения, в котором он родился.

Это важное свойство замыканий плавно подводит нас ко второй концепции:

Возврат функций из функций

Функции, которые работают с другими функциями, либо принимая их в качестве аргументов, либо возвращая их, называются функциями высшего порядка (higher-order functions).

Замыкания позволяют нам вызывать внутреннюю функцию вне ее родительской функции, сохраняя при этом доступ к лексической области видимости родителя.

Обратите внимание, как функция foo возвращает функцию bar. Именно ссылка на bar оказывается в переменной baz после выполнения функции foo. А bar по-прежнему имеет доступ к своему замыканию, например, к идентификатору a.

В последней строчке кода мы выполняем функцию baz за пределами лексической области foo. Казалось бы, в этом месте она никак не может получить доступ к переменной a, чтобы вывести ее в консоль. Но ей это удается благодаря замыканию.

Теперь давайте посмотрим, как мемоизация использует эти концепции.

Последовательность Фибоначчи

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

Задача: написать функцию, которая возвращает n-ный член последовательности Фибоначчи.

Это типичная задача с рекурсивным решением.

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

Эти избыточные вычисления и должна устранить мемоизация.

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

Здесь мы проверяем, был ли получен аргумент memo при вызове функции. Если нет, значит, это первый вызов — берем в качестве кеша пустой объект.

Теперь мы проверяем, есть ли кешированное значение для текущего ключа n, и возвращаем его, если есть.

Как и в предыдущем решении, мы указываем конечный случай, когда n меньше или равно 1.

В конце мы рекурсивно вызываем функцию с уменьшенным значением n, передавая ей кеш.

Обратите внимание, что мы добавляем конечный результат в кеш перед его возвращением.

Проверка производительности с JSPerf

По этой ссылке вы можете перейти на тест производительности нашей функции. Запустите его.

Ничего себе! Это реально впечатляет!

Функция, использующая мемоизацию оказалась намного быстрее.  Она выполняет 126 762 ops/sec, что намного больше, чем чисто рекурсивное решение, которое выполняет 1,751 ops/sec и примерно на 99% медленнее.

Примечание: «ops/sec» означает операции в секунду. То есть, сколько раз в секунду выполняется тест.

Мемоизация может здорово повлиять на производительность приложения. Означает ли это, что придется переписать каждую дорогостоящую функцию с использованием кеша результатов?

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

Функциональный подход

Создадим функцию высшего порядка memoizer, которая позволит нам использовать мемоизацию для любой другой функции, не изменяя ее код.

Мы просто создаем новую функцию под названием memoizer, которая принимает любую функцию fun в качестве параметра. Внутри функции мы создаем объект кеша для хранения результатов выполнения этой функции.

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

Очень удобно! Теперь используем этот мемоизатор для рекурсивной функции Фибоначчи.

Тестирование мемоизатора

Результат тестирования поразителен!

42,982,762 ops/sec! Потрясающая оптимизация.

Итак, мы разобрались, что такое мемоизация, зачем она нужна и как работает. Теперь давайте посмотрим, когда она необходима.

Когда нужна мемоизация?

У вас может возникнуть соблазн мемоизировать все функции без разбора, однако это может оказаться очень непродуктивным. Вот три случая, в которых мемоизация реально полезна:

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

Вот и все! Теперь вы вполне можете использовать мемоизацию в своих проектах.

Комментарии (0)

Ваш email не будет опубликован. Все поля обязательны