Один из первых курсов по разработке программного обеспечения, который я когда-либо посещал, вовлек студентов, воссоздающих известную библиотеку JavaScript Underscore.js с нуля.
Реализация более простых, таких как each или map, была для меня управляемой, но когда мы перешли к более продвинутым, я не смог угнаться. Одной из функций, которая действительно доставила мне много хлопот, была функция memoize. Я образно бился головой об стену с помощью этой функции в течение бесчисленных часов, пока одному из моих коллег не пришлось просто показать мне, как это сделать. Я определенно слишком много думал об этом, и даже после того, как мой коллега объяснил, как это работает, я не полностью понял это.
Столкнувшись с концепцией мемоизации во время изучения React и исследования дополнительных алгоритмических функций, я снова обратился к функции memoize и почувствовал, что понимаю концепцию и реализацию.
Что такое Memoize и когда его использовать?
Согласно документации Underscore, функция
Запоминает заданную функцию, кэшируя вычисленный результат. Полезно для ускорения медленных вычислений.
Memoize принимает в качестве аргумента функцию, которую мы собираемся запомнить. Memoize возвращает функцию, которая принимает неопределенное количество аргументов. Когда вызывается мемоизированная функция (функция, изначально переданная в memoize), memoize проверяет, была ли функция уже вызвана с этим конкретным набором аргументов. Если это так, memoize уже будет иметь результат этого вычисления, сохраненный в его кеше. Таким образом, он найдет его и вернет уже вычисленный результат. Если мемоизированная функция еще не была вызвана с определенным набором аргументов, то memoize выполнит вычисление, сохранит результат в своем кэше и вернет результат.
Зачем это нужно? Допустим, у вас есть действительно «дорогая» функция, которую вы будете часто использовать в своей программе. Вместо того, чтобы вызывать его снова и снова, с помощью memoize вы можете сохранить результат конкретного вычисления, поэтому, если функция вызывается с одним и тем же набором аргументов более одного раза, вам не придется повторять вычисление.
Предостережения и предварительные условия.
1. Синтаксис ES6. Я собираюсь использовать весь синтаксис ES6, поэтому все функции будут стрелочными. Это влияет не только на синтаксис, но и на контекст выполнения ключевого слова this. Я также буду использовать параметр rest вместо объекта arguments, что позволит нам более эффективно использовать встроенные в JavaScript методы Array.
2. Замыкания. Мое любимое определение закрытия - это внутренняя функция, которая имеет доступ к переменным области видимости внешней функции, даже после того, как внешняя функция вернулась. Это будет ключом к реализации нашей функции memoize. Для получения дополнительной информации обратитесь к документации MDN.
3. Функциональные методы / Применить. Функции - это объекты первого класса в JavaScript. Как и у массивов, у них есть методы-прототипы. Применить используется для изменения контекста выполнения функции. Это будет ключевым моментом для нашей реализации, поскольку мы будем иметь дело с функциями как с параметрами, с возвращаемыми функциями и с использованием функций в различных областях. Для получения дополнительной информации обратитесь к документации MDN.
4. Примитивные и сложные типы данных. В нашем примере функция будет оптимизирована только для примитивных данных, таких как строки или числа. Сложные данные передаются по ссылке и потребуют от нас реализации логики, которая проверяла бы, являются ли объекты полностью равными друг другу. Для обзора типов данных в JavaScript обратитесь к документации MDN.
Наша памятная функция
Обычно мы использовали бы это для гораздо более сложных функций, но в этом примере мы собираемся использовать простую функцию сложения, которая принимает неопределенное количество чисел и складывает их все вместе.
const add = (…args) => { return args.reduce((s, e) => { return s += e; }, 0); }
Эта функция использует параметр rest для сбора всех аргументов в массив, а затем использует метод Array reduce, чтобы сложить их все вместе.
Реализация Memoize
Во-первых, memoize принимает функцию, которую мы хотим запомнить как параметр. Затем нам понадобится кеш для хранения ранее вычисленных результатов. Поскольку нам нужно искать значения, нам понадобится что-то с парами "ключ-значение". Итак, мы будем использовать объектный литерал.
const memoize = func => { const cache = {}; }
Memoize возвращает функцию, которая принимает неопределенное количество аргументов.
const memoize = func => { const cache = {}; return (…args) => {} }
Мы захотим узнать, была ли мемоизированная функция вызвана с определенными установленными аргументами или есть путь к ключу, с помощью которого мы можем сохранить вычисление в кеше. Итак, давайте превратим аргументы в строку и сохраним ее в переменной с областью видимости функции.
const memoize = func => { const cache = {}; return (…args) => { let strKey = args.join(','); } }
Мы используем метод join, чтобы превратить все числа в строку, которую мы можем использовать для поиска или хранения, что является нашим следующим шагом.
const memoize = func => { const cache = {}; return (…args) => { let strKey = args.join(‘,’); if(!cache[strKey]){ cache[strKey] = func.apply(this, args); } return cache[strKey]; } } }
В нашем операторе if мы проверяем, была ли мемоизированная функция не вызвана / отсутствует в кеше. В этом случае мы сохраняем его в кеше, используя метод прототипа функции apply для вызова мемоизированной функции в ее новой области действия. Помните, что даже несмотря на то, что мы уже будем работать в глобальной области после возврата внутренней функции, у нас все еще есть доступ к кешу из-за закрытий.
После того, как мы выполним вычисление и сохраним его , внутренняя функция возвращает результат из кеша. Если вычисление уже сохранено в кэше, блок if пропускается и возвращается значение.
Использование Memoize
Давайте применим все это к использованию и запомним нашу функцию добавления, описанную ранее.
const memoize = func => { const cache = {}; return (…args) => { console.log(cache) let strKey = args.join(‘,’); if(!cache[strKey]){ console.log(‘adding to cache!’); cache[strKey] = func.apply(this, args); } console.log(‘fetching from cache!’); return cache[strKey]; } } const add = (…args) => { return args.reduce((s, e) => { return s += e; }, 0); } const memoizedAddFunction = memoize(add); memoizedAddFunction(1, 2, 3); memoizedAddFunction(1, 2, 3); memoizedAddFunction(4, 2, 3); memoizedAddFunction(4, 2, 3); memoizedAddFunction(8, 2, 3); memoizedAddFunction(1, 2, 3); memoizedAddFunction(4, 2, 3); memoizedAddFunction(8, 2, 3);
Вот и все!
Я рекомендую вам запустить эту функцию в среде JavaScript по вашему выбору и добавить еще несколько вызовов * memoizedAddFunction * с еще несколькими / другими номерами. Я включил журналы консоли в разные места в memoize, чтобы вы могли видеть вычисления, добавленные или извлеченные из кеша.
Надеюсь, это поможет прояснить концепцию, которая дала мне много неприятности несколько месяцев назад в буткемпе. Если вам понравилась статья, поставьте мне лайк, поделитесь или прокомментируйте. Если вам ДЕЙСТВИТЕЛЬНО понравилось, выручайте меня, купив мне чашку кофе!