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