Мемоизация в javascript

Зачем использовать мемоизацию

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

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

Допустим, у вас есть некоторая функция sumOf1Bil, которая вычисляет сумму чисел от 0 до 1 миллиарда. Эта функция может быть реализована примерно так:

Здесь я просто использовал цикл for для подсчета от 1 до 1 миллиарда и добавлял все эти числа в аккумулятор одно за другим. В моем браузере это занимает примерно 4 секунды, что в некоторых случаях может быть приемлемым, но будет очень тяжело с точки зрения производительности при включении в цикл.Этот пример еще не запомнен

Кратковременное запоминание

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

Мы реализуем этот метод запоминания, имея словарь ключ-значение (также известный как простой старый объект javascript), живущий в состоянии окна, затем мы напишем функцию memoize, которая принимает обычную функцию и возвращает новую функцию, которая запоминается.

Функция также должна получить ключ, идентифицирующий, какой части кеша принадлежит результат этой функции.

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

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

Давайте реализуем эту новую функцию memoize в нашей старой функции sumOf1Bil:

Теперь, когда мы вызываем sumOf1Bil(), сначала он будет выполняться те же 4 секунды (результат еще не помещен в кеш), но когда мы запустим его снова, он сможет получить результат из кеша, что означает его завершение. работает мгновенно.

Использование хеш-функции для автоматической генерации ключа

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

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

Javascript на самом деле не имеет хорошей сборки для хеширования строки, однако мы можем скопировать/вставить (украсть) очень простой алгоритм хеширования из переполнения стека здесь.

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

Просто добавив эту строку, мы можем исключить использование ключевого параметра. Теперь мы можем просто использовать memoize вот так:

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

А как насчет аргументов функции

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

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

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

Это решение не всегда будет работать, потому что иногда разные аргументы могут привести к одному и тому же ключу, что приведет к конфликту ключей, и функция вернет неправильный результат. Например, f(12,34) приведет к «12,34», а f('12,34') приведет к той же строке. Будьте очень осторожны с этим, потому что, если вы попадете в такую ​​ситуацию, ее будет очень трудно отлаживать.

Долгосрочное кэширование

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

локальное хранилище можно читать и записывать с помощью javascript, используя функции localstorage.getItem(key) и localstorage.setItem(key, value). Чтобы реализовать эту функциональность в нашей функции memoize, вы можете сделать что-то вроде этого:

Заключение

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