Мемоизация в JavaScript - горячая тема для интервью

Википедия определяет мемоизацию

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

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

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

const addTen = function(num){
      return num + 10;
}
console.log(addTen(20)) //Output of this would be 30

Допустим, вы вызываете одну и ту же функцию с одним и тем же аргументом 3 раза, как показано во фрагменте ниже.

const addTen = function(num){
      return num + 10;
}
console.log(addTen(20)) //Output of this would be 30
console.log(addTen(20)) //Output of this would be 30
console.log(addTen(20)) //Output of this would be 30

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

let cache = {};
const addTen = function(num){
        if(num in cache){
          console.log("Inside Memoization block")
          return cache[num]
        }else{
          console.log("Inside Regular execution block")
          cache[num] = num + 10;
          return cache[num]
        }
}
console.log(addTen(20))
console.log(addTen(20))

Результатом приведенного выше фрагмента будет

Inside Regular execution block
30
Inside Memoization block
30

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

Некоторые интервью будут сложными, они зададут довольно сложные вопросы, как показано ниже.

Можете ли вы написать функцию мемоизации для вычисления рядов Фибоначчи?
Можете ли вы написать функцию мемоизации для нахождения факториала числа?

Давайте ответим на вопросы ниже,

Нахождение числа Фибоначчи с помощью мемоизации

Для тех из вас, кто не знает, что такое ряд Фибоначчи: это ряд чисел, где число представляет собой сложение двух последних чисел, начиная с 0 и 1. Пример последовательности: 0, 1, 1, 2 , 3, 5, 8, 13, 21, 34, 55…

Число Фибоначчи 2 равно = 1 + 1 = 2 // фибоначчи (1) + фибоначчи (0)

Сначала давайте посмотрим на обычный рекурсивный подход к вычислению ряда Фибоначчи.

function fibonacci(num) { 
 if (num <= 1) return 1;   
 return fibonacci(num - 1) + fibonacci(num - 2);
}

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

function fibonacci(num, cache) {
  cache = cache || {};
  if (cache[num]) return cache[num];
  if (num <= 1) return 1;
   return cache[num] = fibonacci(num - 1, cache) + fibonacci(num - 2, cache);
}
fibonacci(4,{}) // output is 5

В этой строке

if (cache[num]) return cache[num];

Мы проверяем, вычислены ли уже фибоначчи значения, если оно уже вычислено, мы не будем пересчитывать его, а просто используем это значение. Это улучшит временную сложность алгоритма с 0 (2 ^ n) в предыдущем подходе до 0 (2N) в этом подходе.

Я оставлю читателям подход к нахождению Факториала числа с помощью Memoization. Удачного кодирования !!

Похожие статьи того же автора

Подробнее здесь.

Мемоизация в JavaScript - горячая тема для интервью

Вопросы по теме