Проходя курс Стивена Грайдера «Coding Interview Bootcamp» на Udemy, я наткнулся на технику, называемую мемоизацией, и когда человек может захотеть запомнить функцию. Однако прежде чем мы углубимся, давайте определим, что такое мемоизация.
Что такое мемоизация?
«Мемоизация - это метод оптимизации, при котором дорогостоящие вызовы функций кэшируются, так что результат может быть немедленно возвращен при следующем вызове функции с теми же аргументами».
Это практика записи аргументов каждого вызова функции, чтобы мы могли сохранить результат вызова функции. Если эта функция когда-либо будет вызвана снова с теми же самыми аргументами, вместо того, чтобы запускать функцию и выполнять весь процесс рекурсии, вместо этого мы собираемся вернуть результат, который мы сохранили / вычислили ранее.
Давайте посмотрим на использование мемоизации при решении последовательности Фибоначчи.
Для тех, кто плохо знаком с последовательностью Фибоначчи, это процесс, в котором крайнее правое число вычисляется с использованием двух предшествующих чисел.
fibonacci(8); // => [ 1, 1, 2, 3, 5, 8, 13, 21 ] fibonacci(9); // => [ 1, 1, 2, 3, 5, 8, 13, 21, 34 ] fibonacci(10); // => [ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]
В этом фрагменте кода можно увидеть тенденцию в том, как работает последовательность Фибоначчи. Последний элемент, 55, является суммой двух предшествующих элементов, так же как его предшественник, 34, является суммой двух его предшествующих элементов.
Однако наиболее важным для понимания последовательности Фибоначчи является ее сложность во время выполнения. В то время как итеративное решение имеет сложность выполнения O (n), рекурсивное решение имеет экспоненциальную сложность выполнения O (2 ^ n). Это означает, что для каждого дополнительного элемента, который мы добавляем в нашу коллекцию, или для каждого приращения значения n, мы испытываем резкое увеличение количества вызовов функций, необходимых для вычисления нашего значения.
Как мы можем улучшить время выполнения этого алгоритма?
Вставить мемоизацию
Ниже приведен фрагмент кода базовой реализации мемоизации. Давай пройдемся через это.
function memoize(fn) {
let cache = {};
return function(...args) {
if (cache[args]) {
return cache[args];
}
const result = fn.apply(this, args);
cache[args] = result
return result;
}
}
Мы создаем хранилище или, в данном случае, кеш, в котором мы храним результаты наших вызовов функций. Функция memoize возвращает другую функцию, которая принимает аргументы того, что будет передано в функцию фибоначчи. Затем функция проверяет, существует ли уже в кеше аргумент, с которым вызывается фибоначчи. Если он существует, верните результат этого аргумента, иначе мы собираемся запустить функцию и сохранить оцененный результат с аргументом в качестве ключа. (Если .apply () выглядит чужеродным, Mozilla Developer Network, MDN, является хорошим ресурсом для обзора его реализации)
Vualá. Эта реализация сокращает время выполнения предыдущего экспоненциально-рекурсивного решения до линейного времени.
