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

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

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



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


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

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

function factorial(n) {
    // Вычисления: n * (n-1) * (n-2) * ... (2) * (1)
    return factorial
}

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

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

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

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


Задаваясь вопросом о сохранении результатов предыдущих вызовов функции, мы приходим к идее мемоизации. Это методика, которой функции могут пользоваться для запоминания (или, другими словами, кэширования) результатов. Теперь, когда вы, в общих чертах, понимаете, чего мы хотим достичь, вот более строгое определение мемоизации:
Мемоизация — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ.

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

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

// простая функция, прибавляющая 10 к переданному ей числу
const add = (n) => (n + 10);
add(9);
// аналогичная функция с мемоизацией
const memoizedAdd = () => {
  let cache = {};
  return (n) => {
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result');
      let result = n + 10;
      cache[n] = result;
      return result;
    }
  }
}
// эту функцию возвратит memoizedAdd
const newAdd = memoizedAdd();
console.log(newAdd(9)); // вычислено
console.log(newAdd(9)); // взято из кэша

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


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

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

  • Переменная cache может хранить данные между вызовами функции, так как она определена в замыкании.

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

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


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

// простая чистая функция, которая возвращает сумму аргумента и 10
const add = (n) => (n + 10);
console.log('Simple call', add(3));
// простая функция, принимающая другую функцию и
// возвращающая её же, но с мемоизацией
const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];  // тут работаем с единственным аргументом
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result');
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  }
}
// создание функции с мемоизацией из чистой функции 'add'
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3));  // вычислено
console.log(memoizedAdd(3));  // взято из кэша
console.log(memoizedAdd(4));  // вычислено
console.log(memoizedAdd(4));  // взято из кэша

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

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


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


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

// уже знакомая нам функция memoize
const memoize = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];
    if (n in cache) {
      console.log('Fetching from cache', n);
      return cache[n];
    }
    else {
      console.log('Calculating result', n);
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  }
}
const factorial = memoize(
  (x) => {
    if (x === 0) {
      return 1;
    }
    else {
      return x * factorial(x - 1);
    }
  }
);
console.log(factorial(5)); // вычислено
console.log(factorial(6)); // вычислено для 6, но для предыдущих значений взято из кэша

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

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

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


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

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


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

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

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

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

  • Если вы работаете с React/Redux, можете взглянуть на reselect. Тут используется селектор с мемоизацией. Это позволяет выполнять вычисления только в том случае, если в соответствующей части дерева состояний произошли изменения.

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

Уважаемые читатели! Если у вас есть примеры использования мемоизации в реальных проектах — поделитесь пожалуйста. Уверены, многим будет интересно о них узнать.
RUVDS.com
1,482.32
RUVDS – хостинг VDS/VPS серверов
Share post

Comments 39

    0
    Всегда считал, что слово «момоизация» говорят только в контексте задач динамического программирования. Иначе не совсем понятно, зачем еще один термин, обозначающий то, что все привыкли называть кэшированием?
      +1
      Кэш это более широкое понятие, он может быть не только в памяти, и не только кэшем результатов.
        +2

        Кэширование — более общий термин, потому что кэшировать можно любые данные, а мемоизировать — только неизменяемые.

          +1
          Настолько витающий в воздухе приём имеет право вообще никак не называться.
            0

            Но только до тех пор, пока он не имеет отражения в коде в виде функция высшего порядка или декоратора. Потому что надо же как-то эту функцию назвать… :-)

          –2
          Так для всего этого можно генераторы использовать
            0
            Не совсем понял что это дает, хотелось бы увидеть какие то тесты производительности.
              +1
              Тесты производительности будут зависеть от того какие именно функции мемоизируются. На синтетическом тесте можно и тысячекратный прирост производительности нарисовать.
              0
              Очень полезная информация для меня, спасибо. Тут главное применять там где нужно. При разработке интерфейсов, возможно прибегание к мемоизации может быть избыточным.
                0
                Крайне узкая область применения… Подавляющее большинство функций во фронтэнде должны что-то делать, а не возвращать какой-то результат. Менять DOM, выполнять запросы, генерить события и т.п. Как часто вы считаете факториал на фротэнде?
                  0
                  В мире реакта, редукса и чистых функций — совсем не лишний подход.
                    –2

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

                      0

                      Почему все JS'ники называют обычную передачу переменной по ссылке "реактивным программированием"?

                        0

                        Почему вы называете обновление группы связанных переменных по динамически выявленному графу зависимостей "обычной передачей по ссылке"?

                      +1

                      Разделяйте функции, делающие что-то, и функции, возвращающие что надо делать :) Это хороший подход даже без нацела на мемоизацию.

                        +2
                        Подавляющее большинство функций во фронтэнде должны что-то делать, а не возвращать какой-то результат.

                        Не зовите функциями процедуры

                          0
                          порой можно кэшировать элемент DOM, не повторяя его поиск при каждом вызове
                          –1

                          А если к мемоизации добавить трекинг зависимостей и автоматическую очистку кеша, то получится реактивное программирование :-)

                            +1
                            Оптимизатор v8 сам умеет чекать «чистые» функции и применять к ним мемоизацию, притом с гораздо более умным кэшем, из которого со временем удаляются редко используемые значения, освобождая тем самым память
                            подобные оптимизации — пережиток далекого прошлого
                            более того, подобная «оптимизация» может даже замедлить код
                              +1
                              Закладываться на то, что некий интерпретатор оптимизирует ваш код, не совсем правильно, а завтра он это делать перестанет, да и код выполняется в разных окружениях.
                                0

                                А в остальных браузерах что?)

                                0

                                Вы просили реальные примеры, правда они больше подходят под слово кеширование. Был не очень адекватный клиент, который выгружал себе на страницу 50000 записей, и начинал сортировку по дате. Разумеется жаловался на то, что как-то медленно все работает. Компаратор по датам у нас был реализован относительно просто, но не оптимально. Что мы сделали: даты (как строки) преобразовывали в числа и сравнивали числа между собой, чтобы не делать постоянное преобразование из строки в число мы сделали кеш значений строка->число. Также использовали тот факт, что даты(без времени) имеют ограниченный набор реальных значений: сегодня, вчера, позавчера, максимум пол года назад, т.е кеш строк был примерно размером не более 365 записей всего. Увеличили скорость сортировки в 16 раз

                                  –1
                                  Уже давным давно иммутабельность рулит с redux, а тут эхо прошлого. Давайте еще о замыканиях вспомним коли на то пошло.
                                    +1

                                    Во-первых, с redux довольно успешно конкурирует mobx, где иммутабельности нет и не предвидится.


                                    Во-вторых, с чего вы взяли, что мемоизация плохо сочетается с иммутабельностью?

                                      +1
                                      Если вы работаете с React/Redux, можете взглянуть на reselect. Тут используется селектор с мемоизацией.

                                      Без реселекта у вас более-менее сложное приложение будет тупить.

                                      0

                                      Как известно, две самые сложные проблемы в программировании — это дать имя переменной и инвалидация кэша. Ожидал здесь увидеть про последнее, тем более после слов «это разновидность кэширования». И что там с памятью? Как будто статья для детей, а не Хабра. Ах, да...

                                        0

                                        Мемоизация — это "вечное" кеширование неизменяемых данных. Такой кеш не нуждается в инвалидации.

                                          0

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

                                            +2

                                            Так тут нужна не инвалидация, а очистка. А для мемоизации существуют способы очистки

                                          +1

                                          По сути мемоизации кэш при ней всегда валиден. Не может вдруг измениться результат fact(100500) так, чтобы предыдущий результат стал не валиден.

                                            –1

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

                                              0

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


                                              Вы как бы и отсутствие значения (не завершился запрос) считаете за исключительную ситуацию, что уж тут.

                                                –1

                                                Всё зависит от критериев валидности, которые (внезапно!) могут быть разными и в том числе такими: "кеш считается валидным, если есть вероятность его дальнейшего полезного применения".


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

                                                  +1
                                                  "кеш считается валидным, если есть вероятность его дальнейшего полезного применения".

                                                  У вас достаточно странное мышление. Мне, все же, как-то привычней разделять понятия валидности и необходимости.


                                                  Для синхронного кода ожидающего результат ситуация действительно исключительная

                                                  Тоже не соглашусь. Исключительная ситуация — это когда бэк пятисотит или что-то вроде. А то, что данных нет — это часть состояния, которое должно быть корректно обработано. Более того, мне очень по душе подход с использованием ADT, когда "нет данных" — это тоже данные, но с другим типом. Более того, можно даже исключительных ситуаций для потребляющего кода избежать, используя любой аналог Either.

                                                    0

                                                    По вашему рассматривать отсутствие данных как исключительную ситуацию (заметьте, не ошибку) — это странное мышление, а рассматривать ошибку как данные — нет?

                                                      0

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


                                                      Отсутствие данных — это тоже данные, вы же отображаете где-то спиннер. Значит это часть вашего стейта.
                                                      Ошибка, ну например 404, это значит данные не найдены, надо опять что-то в интерфейсе показать. Значит это часть вашего стейта.
                                                      Даже 500, великий и ужасный, тоже требует какой-то реакции интерфейса. Значит это… ну вы поняли.


                                                      Я хочу сказать, что имею в виду следующий подход:
                                                      Раз, два, три.

                                                        0

                                                        Такой подход великолепно сочетается с FRP (про ORP не скажу). Мы правда на Rx сидим, но, думаю, в $mol тоже зайдет. Не пробовали?

                                                          +1

                                                          Для FRP нужно много разных костылей. Для ОРП они просто не нужны — вы пишете простой и ясный код, предполагающий, что данные у вас есть. Именно в этом прелесть исключений — вы пишете позитивную логику, а всякие исключительные ситуации (произошла ошибка, нужно подождать и тп) прерывают позитивную логику, передавая управление сразу в общий обработчик таких ситуаций. Именно поэтому в $mol проблемы "забыл проверить флаг loading" не стоит в принципе — типовую обработку ошибок и ожиданий берёт на себя рендерер, чего хватает в подавляющем большинстве случаев. А когда нужна кастомизация обработки исключительных ситуаций — есть try-catch.

                                                          0

                                                          Вы немного ошибаетесь. Необработанные ситуации как правило называются ошибками (Error) или отказами (Fault). А исключения — это ситуации, требующие особой обработки.

                                          Only users with full accounts can post comments. Log in, please.