Мои любимые разделы компьютерных наук — это вещи, которые напоминают мне о том, что я человек. Хотите верьте, хотите нет. Компьютеры обладают этим эмерджентным свойством: по мере усложнения они начинают делать то же самое, что и мы, люди. Мы коснулись этого, когда я писал о рекурсии. Там я обсуждал, как компьютерная функция будет вызывать себя снова и снова, пока не получит желаемый ответ. Это так… по-человечески, и для меня это касается решения проблем. Мемоизация может еще больше расширить это человеческое качество.
Интуитивно понятно, что мемоизация — это локальное запоминание компьютерной программы. Допустим, вы пишете функцию, которая вызывается. Если та же функция вызывается снова с теми же входными данными, она должна возвращать тот же результат. Это известно как функциональное программирование, состоящее из чистых функций; здесь все ссылочно, и если вы замените вызов функции возвращаемым значением функции, программа будет вести себя точно так же. Ниже приведен пример для демонстрации: вы можете поместить в свою программу квадрат (10) или 100, и она будет работать аналогично:
const square = (x) => x*x square(10) /* square is a pure function that is referential you could place 100 wherever you place square(10) and get the same result */
Мемоизация учит вашу программу запоминать в реальном времени. Это будет очень полезно для вашей программы и остановит временную сложность. Первое, что нужно сделать, это настроить массив или объектный литерал, который будет служить памятью (да, это намеренная шутка). Давайте поэкспериментируем и создадим функцию, которая создает удобочитаемые телефонные номера. Мы начнем с создания литерала объекта phoneBook для хранения наших телефонных номеров.
const phoneBook = {}
Наша функция примет строку чисел и превратит ее во что-то, отформатированное так, чтобы человек знал, что это телефонный номер:
humanPhoneNumber("dddddddddd") //=>(ddd)ddd-dddd
Первое, что сделает эта функция, это проверит, не обрабатывался ли уже наш номер в нашей функции phoneBook. Мы устанавливаем ключ объекта на необработанное число, а значением будет обработанная форма, возвращаемая функцией. Если наша функция найдет номер в нашей телефонной книге по необработанному ключу, она просто вернет обработанное значение. В противном случае она запустит функцию, обработает номер, сохранит номер в телефонной книге и вернет его.
Давайте проверим нашу память, чтобы увидеть, сколько времени мы экономим.
Node.js имеет функцию performance.now(), которая создаст отметку времени.
Давайте настроим несколько вызовов функций до того, как номер будет в телефонной книге, и после, чтобы увидеть, сколько времени занимает наша функция. Давайте вызовем функцию с новым номером. Затем мы позвоним ему еще раз и посмотрим, сколько времени потребуется во второй раз, чтобы просто воспользоваться нашей телефонной книгой.
Посмотрим, что мы получим в нашем терминале:
Давайте обсудим эту распечатку. Время, необходимое для выполнения начального вызова функции, составило 0,625 миллисекунды. Как вы можете видеть на картинке, функция обрабатывает случайное число. Затем мы снова вызываем функцию с исходным номером телефона. Второй раз; время, когда номер находится в нашей телефонной книге, заняло 0,003 миллисекунды. Миллисекунды едва ощутимы. Однако, если вы работаете в телефонной компании и постоянно обрабатываете этот номер, этот номер начнет иметь значение. Это незначительное количество времени начнет накапливаться, пока не станет иметь значение.
