Научитесь использовать и применять мемоизацию, чтобы сэкономить время в вызовах JS
Помимо учета временной сложности для оптимизации времени выполнения, мемоизация - еще одна эффективная стратегия, позволяющая снизить скорость выполнения вашего кода. К счастью для нас, этот метод довольно прост для понимания и применения при среднем или хорошем понимании JavaScript.
Сначала разберем определение.
Сломай
В вычислениях мемоизация или мемоизация - это метод оптимизации, используемый в основном для ускорения компьютерных программ путем сохранения результатов дорогостоящих вызовов функций и возврата кэшированного результата. когда те же входы повторяются снова. - Википедия
Когда я снова перечитываю определение, я убеждаюсь, что знаю, что означает каждое слово, и как я могу, по сути, наметить план для создания функции мемоизации. Это создает дорожную карту того, как я буду псевдокодировать, и, наконец, фактически закодирую свою функцию запоминания.
Я хотел бы сосредоточиться на второй половине определения.
Начнем со следующего:
«сохранение результатов вызовов дорогостоящих функций»
Все это говорит о том, чтобы сохранить результаты вызова в какой-то структуре данных. Естественно, мы будем стремиться к структуре данных, подобной словарю, где вы можете хранить данные в соответствии с каким-то заданным вводом (ключевое значение paris). Поэтому для этого сценария мы хотим использовать какую-то хеш-таблицу, а именно Objects
или Maps
. Эта статья гласит следующее:
«В хеш-таблицах вставка и поиск в среднем имеют постоянное время. Из-за столкновений и изменения размера эти незначительные затраты могут вырасти до линейного времени ».
let myObj = {} // or let myMap = new Map()
Есть плюсы и минусы использования Objects
вместо Maps
и наоборот. Например, в Maps
пары ключ и значение могут относиться к любому объектному или примитивному типу данных, тогда как для Objects
ключи ограничены только типами данных string
и symbol
. Кроме того, для перебора Objects
необходимо вызвать Object.keys(myObj)
; проще в Maps
вы можете сопоставить пары ключ-значение, вызвав метод-прототип myMap.entries()
.
Для этого небольшого примера я предпочитаю использовать Object
, потому что это то, с чем у меня больше опыта, и преимущества оптимизации незначительны при использовании Map
для этого сценария.
Давайте продолжим анализ:
«… и возвращение кешированного результата, когда те же входные данные повторяются снова».
Таким образом, при том же вводе в функции n
, вместо повторного вызова функции мы вернем результат кэшированный, когда такие же вводы будут повторяться снова. Готовы ли вы применить то, что мы узнали?
Давайте код!
Итак, теперь, когда у нас есть план на игру, мы готовы к его реализации. Повторюсь, для конкретного function
мы сохраним наши результаты при первом вызове в object
. Если функция вызывается снова с тем же вводом, мы вернем кешированный результат вместо повторного вызова функции.
Здесь мы хотим создать функцию более высокого порядка, которая, по сути, является функцией, которая принимает функцию в качестве аргумента и возвращает другую функцию. Давайте посмотрим на классическую функцию Фибоначчи:
Напомним, что исходная рекурсивная функция вызывалась более 40 миллиардов раз для вычисления 50-го числа Фибоначчи. При реализации мемоизации это число снижается до 99.
Заключение
Мы можем использовать мемоизацию как функцию более высокого порядка, чтобы уменьшить количество вызовов JavaScript, так что нам нужно выполнять только те вызовы, которые мы не выполняли в прошлом. Это может быть применено к результатам, которые зависят от меньших ранее введенных данных (в которых мы можем сэкономить время на рекурсию), или к строке поиска, где мы можем кэшировать результаты, которые мы уже получили от API. Вы можете использовать мемоизацию как инструмент, чтобы добавить некоторые изящные аксессуары к уже существующим функциям и создать свой собственный частный кеш внутри закрытия.
Ресурсы:
Структуры данных в JavaScript - Silicon Wat
Реализация мемоизации в JavaScript - Колин Ириг
Понимание мемоизации JavaScript за 3 минуты - Codesmith