Во время моего первого собеседования по программированию на месте я столкнулся с концепцией, которую никогда раньше не видел. Я не помню вопрос дословно, но он звучал примерно так:

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

//Given reducer method: 
function add(a,b){
 return a+b
}
//Create a method called memoize such that: 
const memoizeAdd = memoize(add);
//then calling…
memoizeAdd(100,100); //returns 200
memoizeAdd(100); //returns 100
memoizeAdd(100,200) //returns 300
memoizeAdd(100,100) //returns 200 without computing

Так вот я думаю… дерьмо. Мне никогда раньше не приходилось использовать кеширование, как, черт возьми, я собираюсь ответить на этот вопрос !? Затем я вспомнил, что слышал термин мемоизация и даже ИСПОЛЬЗОВАЛ его в своем последнем проекте React Native. Если я правильно помню, у меня возникли проблемы с производительностью, я искал некоторые возможные решения в StackOverflow и нашел React.memo допустимым решением. Тем не менее, я, должно быть, подсознательно упустил из виду то, как на самом деле работает мемоизация.

К счастью, это было интервью с венчурным капиталистом, поэтому мне потребовалось несколько секунд, чтобы поискать в Google: Что, черт возьми, это функция Memoize? (ну… что-то в этом роде). Я нашел пример кода, приведенный ниже, и использовал его как ссылку, чтобы помочь ответить на оставшийся вопрос.

// a simple function to add something
const add = (n) => (n + 10);
add(9);
// a simple memoized function to add something
const memoizedAdd = () => {
  let cache = {};
  return (n) => {
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result');
      let result = n + 10;
      cache[n] = result;
      return result;
    }
  }
}
// returned function from memoizedAdd
const newAdd = memoizedAdd();
console.log(newAdd(9)); // calculated
console.log(newAdd(9)); // cached

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

Что делает мемоизация

Вот краткое и точное объяснение мемоизации функций:

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

Примечание. В этом сценарии не нужно применять кеш браузера.

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

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

Простой пример мемоизации

Давайте для демонстрации создадим простую функцию Memoize, подобную показанной выше.

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

const memoize = (fn) => {}

Затем давайте объявим начальный объект кеша.

const memoize = (fn) => {
   let cache = {}
}

Большой. А теперь давайте вернем что-нибудь. Сначала мы реализуем возможность №1 - «Если ввод использовался раньше, найдите его в кеше и немедленно верните сохраненное значение без выполнения каких-либо дальнейших вычислений».

const memoize = (fn) => {
   let cache = {}
   return (n) => {
      if (n in cache){
         return cache[n]
      }
}

Давайте рассмотрим. Прежде всего, memoize официально стал функцией высшего порядка, потому что он принимает функцию в качестве ввода и / или возвращает функцию в качестве вывода. Чтобы уточнить детали, если мы вызовем memoize, мы получим другую функцию, которая проверяет, является ли данный параметр n ключом в cache и вернет соответствующее значение. Что в этом особенного? Дело в том, что возвращенная функция имеет в своей области кеш, где она может получать доступ к свойствам или добавлять их! В дальнейшем это может оказаться очень мощным.

На данный момент объект кеша останется пустым, поэтому давайте реализуем правило № 2, чтобы изменить это - «Используйте ввод для выполнения любых необходимых вычислений, сохраните результаты в кеше, верните результат».

const memoize = (fn) => {
   let cache = {}
   return (n) => {
      if (n in cache){
         return cache[n]
      }else{
         let result = fn(n);
         cache[n] = result;
         return result;
      }
   }
}

Потрясающие! Теперь, если параметр n не был сохранен в кеше, memoize выполнит вычисление fn (n), а результат результат будет сохранен в кеше так:

/* Given n=5 and result=15, cache will contain the 
key:value pair of: */
"5" : 15

Давайте посмотрим на это в действии.

Во-первых, учитывая функцию add10

const add10 = (n) => n + 10

Мы можем объявить memoizeAdd10 как

const memoizeAdd10 = memoize(add10);

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

memoizeAdd10(15); //returns 25
memoizeAdd10(20); //returns 30
memoizeAdd10(25); //returns 35

После этих вызовов кеш memoizeAdd10 будет выглядеть следующим образом:

{
   "15" : 25,
   "20" : 30,
   "25" : 35
}

И если мы назовем что-то вроде

memoizeAdd10(15); //returns 25 without arithmetic computations

в другой раз - вместо вычисления результата memoizeAdd10 просто погрузится в кеш, найдите ключ «15 ” и вернет 25 без выполнения каких-либо вычислений. Вы можете подумать: «но это просто функция добавления, которая почти не нагружает нашу машину, кого это волнует?» Конечно, но когда алгоритмы вырастают от простого добавления к рекурсивным операциям, например, мемоизации может оказаться огромным преимуществом.

Решение нашего вопроса на собеседовании

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

В этом примере мы изменили примерно 3 вещи. Пройдемся по ним:

  1. n ➡️ … args (строка3) - функция возврата теперь принимает неопределенное количество параметров, к которым можно получить доступ с помощью массива args или объекта arguments.
  2. «cacheKey» (строки 4, 5, 6, 9) - мы объявили переменную с именем «cacheKey», которая представляет имя ключа. (ранее «n»), который будет использоваться либо для доступа к кешу, либо для объявления нового свойства кеша. Это изменение сделано для того, чтобы отслеживать несколько входов. Мы формируем cacheKey, отображая массив «args» и возвращая строку « n » и« + ». Например, при вызове memoizeAdd (10, 20, 30) cacheKey будет «10 + 20 + 30 +».
  3. fn (n) ➡️ args.reduce ((acc, curr) =› fn (acc, curr), 0) - из-за того, что memoizeAdd может принимать любое неопределенное количество параметров, чтобы найти сумму всех параметров, мы можем использовать Array.prototype.reduce .

Используя нашу недавно обновленную функцию memoize, после выполнения следующих вызовов функций

memoizeAdd(10, 20, 30, 40); //returns 100
memoizeAdd(1, 2, 3, 4); //returns 10
memoizeAdd(5, 10) //returns 15

наш кеш будет выглядеть примерно так:

{
   "10+20+30+40+" : 100,
   "1+2+3+4+" : 10,
   "5+10+" : 15
}

Затем, если мы позвоним снова:

memoizeAdd(1, 2, 3, 4); //returns 10 without arithmetic computations

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

Заключение

Мы только что продемонстрировали возможности мемоизации функций в JavaScript. Надеюсь, вам понравилось читать, и вы подумаете об использовании этого метода в своем следующем проекте! Спасибо!