Введение

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

Понимание мемоизации

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

Запоминание — распространенный метод повышения производительности. Если вы используете React, вы определенно использовали React.memo раньше.

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

Итак, не могли бы вы реализовать общую функцию memo(), которая кэширует результат после вызова, поэтому при передаче одних и тех же аргументов результат будет возвращен немедленно.

Написание функции мемоизации

Давайте создадим функцию запоминания общего назначения в JavaScript:

function memo(func) {
  let cache = {};
  
  return function(...args) {
    let key = JSON.stringify(args);
    if(cache[key]) {
      return cache[key];
    }
    else {
      let val = func.apply(null, args);
      cache[key] = val;
      return val;
    }
  };
}

Функция memoize — это функция высшего порядка, которая принимает функцию func в качестве аргумента. Он поддерживает cache для отслеживания результатов вызовов функций.

Функция, возвращаемая memoize, принимает переменное количество аргументов (...args). Он создает ключ, упорядочивая эти аргументы, и проверяет, есть ли уже результат для этих аргументов в файле cache. Если это так, он возвращает кэшированный результат; в противном случае она вызывает исходную функцию с этими аргументами, сохраняет результат в cache и возвращает результат.

Решение с резольвером:

/**
 * @param {Function} func
 * @param {(args:[]) => string }  [resolver] - cache key generator
 */
function memo(func, resolver = (...args) => args.join('_')) {
  const cache = new Map();

  return function(...args) {
    const cacheKey = resolver(...args);
    if (cache.has(cacheKey)) {
      return cache.get(cacheKey);
    }
    const value = func.apply(this, args);
    cache.set(cacheKey, value);
    return value;
  }
}

Тестирование функции запоминания

Пример 1: Последовательность Фибоначчи

Начнем с классической рекурсивной задачи — последовательности Фибоначчи:

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

const fastFibonacci = memo(slowFibonacci);

console.log(fastFibonacci(40)); // First time computation
console.log(fastFibonacci(40)); // Instant return from cache

Функция slowFibonacci представляет собой простую реализацию последовательности Фибоначчи, которая требует значительных вычислительных ресурсов для больших входных данных.

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

Пример 2: Факторный расчет

Теперь давайте рассмотрим еще одно распространенное рекурсивное вычисление: факториал числа.

function slowFactorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * slowFactorial(n - 1);
  }
}

const fastFactorial = memo(slowFactorial);

console.log(fastFactorial(10)); // First time computation
console.log(fastFactorial(10)); // Instant return from cache

Пример 3: Самая длинная общая подпоследовательность

Проблема самой длинной общей подпоследовательности (LCS) — это классическая проблема информатики, которую часто решают с помощью динамического программирования. Однако наивное рекурсивное решение крайне неэффективно из-за повторяющихся вычислений. Давайте посмотрим, как мемоизация может оптимизировать это.

function slowLCS(X, Y, m, n) {
  if (m === 0 || n === 0) {
    return 0;
  }
  if (X[m - 1] === Y[n - 1]) {
    return 1 + slowLCS(X, Y, m - 1, n - 1);
  } else {
    return Math.max(slowLCS(X, Y, m, n - 1), slowLCS(X, Y, m - 1, n));
  }
}

const fastLCS = memo(slowLCS);

console.log(fastLCS('ABCBDAB', 'BDCAB', 7, 5)); // First time computation
console.log(fastLCS('ABCBDAB', 'BDCAB', 7, 5)); // Instant return from cache

Пример 4: Проблема размена монет

Проблема размена монет — еще одна классическая задача, которую можно решить с помощью методов динамического программирования. Задача состоит в том, чтобы найти количество способов, которыми мы можем получить сдачу на определенную сумму при бесконечном запасе монет определенного номинала. Вот как вы можете решить ее с помощью запоминания:

function slowChange(coins, m, n) {
  if (n == 0) return 1;
  if (n < 0) return 0;
  if (m <= 0 && n >= 1) return 0;
  return slowChange(coins, m - 1, n) + slowChange(coins, m, n - coins[m - 1]);
}

const fastChange = memo(slowChange);

console.log(fastChange([1, 2, 3], 3, 4)); // First time computation
console.log(fastChange([1, 2, 3], 3, 4)); // Instant return from cache

Заключение

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

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

Удачного кодинга 🚀

Дополнительные материалы на PlainEnglish.io.

Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .