Первоначально опубликовано на www.carloscaballero.io 8 февраля 2019 г.

Что означает мемоизация?

Определение мемоизации из Википедии следующее:

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

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

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

На следующей анимации вы можете увидеть окончательный результат применения мемоизации в нашем коде.

Что такое чистая функция?

Чистая функция - это функция, отвечающая следующим критериям:

  1. Это функция, которая всегда возвращает один и тот же результат, если аргументы совпадают. Например, следующие функции нечисты:
  • Функции, использующие случайные числа.
  • Функции, которые используют datetime в качестве начального числа для генерации результата.
  1. Это функция, которая не вызывает побочных эффектов в приложении:
  • Мутация данных или изменение состояния приложения.
  • Сетевой запрос.
  • База данных или запрос файла.
  • Получение пользовательского ввода.
  • Запрос DOM.

Преимущества

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

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

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

Пример чистых функций

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

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

Еще один интересный пример чистых функций:

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

Мемоизация - это метод программирования, который позволяет не пересчитывать значение чистой функции. То есть чистые функции возвращают одно и то же значение при одинаковых входных данных. Таким образом, возвращаемое значение может быть сохранено в системе с использованием любой системы кеширования (например, карты или массива). Итак, если вы вычисляете значение factorial(1), вы можете сохранить возвращаемое значение 1, и одно и то же действие может выполняться при каждом выполнении. Итак, когда вы запускаете факториал (100), вам нужно время в первый раз, но во второй и более раз время будет сокращено!

В этом случае, если вы обратите внимание на рекурсивную факториальную версию, вы можете заметить, что эта версия несколько раз выполняет функцию factorial, которая может быть кэширована в нашей системе (с использованием мемоизации), но если вы используете императивную факториальную версию, ваша производительность будет хуже. По этой причине memoization - хорошо известный метод в декларативных языках.

Пример запоминания! - Живой код!

В этом разделе я покажу вам, как реализовать мемоизацию с помощью closure и шаблона decorator с помощью JavaScript.

Шаблон декоратора позволяет добавлять новые функции к любому объекту во время выполнения, используя композицию вместо иерархии. Цель шаблона - избежать создания иерархии классов наших функций.

Хороший пример для понимания этого шаблона можно найти в Блоге Адди Османи.

Итак, базовая реализация декоратора memoize в JavaScript следующая:

  1. Определите кеш, в котором будет храниться результат выполнения. Мы используем объект как map для хранения этих результатов.
  2. Декоратор возвращает новую функцию, которая имеет то же поведение, что и исходная функция, но реализована мемоизация.
  3. Ключ карты "ключ-значение" создается с использованием stringify и аргументов исходной функции.
  4. result новой функции будет
  5. Выполнение исходной функции (fn(...args)) независимо от того, нет ли хранилища в кеше.
  6. Значение, хранящееся в кеше (независимо от того, было ли оно предварительно рассчитано ранее).
  7. result возвращается.

Как использовать наш memoized декоратор?

Использовать этот декоратор с помощью JavaScript очень просто:

В этом случае функция add - это исходная функция без мемоизации, а функция addMemoized - это новая функция, которая имеет новую функцию (мемоизация) с использованием шаблона декоратора.

Настоящая демонстрация с использованием мемоизации!

А теперь я покажу вам настоящего мастера использования мемоизации. Представьте себе сложный алгоритм, который указывает вам, имеет ли array уникальное значение (например, Array.prototype.some), но ужасно запрограммированное.

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

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

Массив создается в начале скрипта:

И, наконец, когда пользователь нажимает кнопку, функции выполняются.

  1. Нет мемоизации

2. Воспоминание

Результат показан на следующей анимации:

Выводы

Мемоизация получила широкое распространение в веб-разработке с использованием TypeScript или JavaScript. Следующий список ресурсов должен стать отправной точкой для их использования в ваших проектах.

Fast-Memoize используйте этот график для сравнения различных реализаций memoize:

Больше теории:

Первоначально опубликовано на www.carloscaballero.io 8 февраля 2019 г.