Воспоминание. Улучшение рекурсивного решения проблемы последовательности Фибоначчи.

В моем недавнем сообщении в блоге о последовательности Фибоначчи были описаны итеративный и рекурсивный подходы к решению этой общей проблемы интервью. Напоминаем, что задача звучала так: Напишите функцию, возвращающую n элементов в последовательности Фибоначчи.

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

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

Для нашего рекурсивного решения мы хотим сохранить аргументы каждого вызова функции, а также вывод функции, и повторно использовать их позже, если функция вызывалась с теми же аргументами.

Наше рекурсивное решение выглядело так:

function fib(n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

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

function memoize(fn){
  const cache = {}
  return function(){
  }
}

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

function memoize(fn){
  const cache = {}
  return function(...args){
  }
}

Отсюда нам нужно будет заглянуть в наш банк памяти, нашу константу кеша, и если он содержит ключ с этим набором аргументов, мы вернем соответствующее значение.

function memoize(fn){
  const cache = {}
  return function(...args){
    if (cache[args]){
      return cache[args];
    }
  }
}

Если функция никогда не вызывалась с текущим набором аргументов, нам придется передать их исходной медленной функции, то есть fn, переданной в memoize в качестве аргумента, а затем сохранить результат в кеш. . Чтобы передать массив аргументов, нам нужно использовать метод apply ().

function memoize(fn){
  const cache = {}
  return function(...args){
    if (cache[args]){
      return cache[args];
    }
    newCall = fn.apply(null, args);
    cache[args] = newCall;
    return newCall;
  }
}

Чтобы использовать функцию memoize для нашей проблемы Фибоначчи, мы просто сохраняем вызов функции memoize как константу и передаем аргументы, которые в противном случае были бы переданы в fib этой константе.

const fastFib = memoize(fib);

И, наконец, нам нужно убедиться, что когда fib выполняет рекурсивные вызовы, он вызывает новую быструю версию самого себя, а не оригинального self.

const fastFib = memoize(fib);
function fib(n) {
  if (n < 2) {
    return n;
  }
  return fastFib(n - 1) + fastFib(n - 2);
}

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

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

Как всегда, спасибо за чтение и удачного кодирования!