В погоне за производительностью разработчики изобретают самые разные способы оптимизации программ. В нашем случае речь идёт о повышении скорости работы функций. Пожалуй, в JavaScript их по праву можно назвать одним из краеугольных камней языка. В частности, функции — это средство разбиения программ на модули и инструмент для повторного использования кода.
Некоторые функции выполняются так быстро, что их многократный вызов, хотя и создаёт нагрузку на систему, проблемой не является. Некоторые же весьма «тяжелы», каждое обращение к таким функциям ведёт к серьёзным затратам вычислительных ресурсов. Если траты оправданы, вычисления оптимизированы, то деваться особо некуда. Но как быть, если при повторных вызовах, функция иногда (или, возможно, довольно часто) выполняет те же самые вычисления, которые выполнялись при её предыдущих вызовах? Можно ли этим воспользоваться для повышения производительности?
factorial
, которая вычисляет и возвращает факториал числа. Если не вдаваться в детали её реализации, выглядеть она будет так:function factorial(n) {
// Вычисления: n * (n-1) * (n-2) * ... (2) * (1)
return factorial
}
factorial(50)
. Она, как и ожидается, найдёт и возвратит факториал числа 50. Всё это хорошо, но давайте теперь найдём с её помощью факториал числа 51. Компьютер снова выполнит вычисления, и то, что нам надо, будет найдено. Однако, можно заметить, что, при повторном вызове, функция выполняет массу вычислений, которые уже были выполнены ранее. Попытаемся функцию оптимизировать. Подумаем, как, имея значение factorial(50)
перейти к factorial(51)
без повторного вызова функции. Если следовать формуле вычисления факториала, окажется, что factorial(51)
это то же самое, что и factorial(50) * 51
.factorial()
производится полная цепочка вычислений для нахождения факториала 50, а потом то, что получилось, умножается на 51. То есть, при использовании подобной функции, вычисление факториала для числа 51 в любом случае выглядит как перемножение всех чисел от 1 до 51.factorial()
умела запоминать результаты вычислений, выполненных при её предыдущих вызовах и использовать их при следующих вызовах для ускорения производительности.Мемоизация — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ.
// простая функция, прибавляющая 10 к переданному ей числу
const add = (n) => (n + 10);
add(9);
// аналогичная функция с мемоизацией
const memoizedAdd = () => {
let cache = {};
return (n) => {
if (n in cache) {
console.log('Fetching from cache');
return cache[n];
}
else {
console.log('Calculating result');
let result = n + 10;
cache[n] = result;
return result;
}
}
}
// эту функцию возвратит memoizedAdd
const newAdd = memoizedAdd();
console.log(newAdd(9)); // вычислено
console.log(newAdd(9)); // взято из кэша
memoizeAdd
возвращает другую функцию, которую мы можем вызвать тогда, когда нужно. Такое возможно потому что функции в JavaScript — это объекты первого класса, что позволяет использовать их как функции высшего порядка и возвращать из них другие функции.cache
может хранить данные между вызовами функции, так как она определена в замыкании.cache
ведёт себя именно так, как ожидается.// простая чистая функция, которая возвращает сумму аргумента и 10
const add = (n) => (n + 10);
console.log('Simple call', add(3));
// простая функция, принимающая другую функцию и
// возвращающая её же, но с мемоизацией
const memoize = (fn) => {
let cache = {};
return (...args) => {
let n = args[0]; // тут работаем с единственным аргументом
if (n in cache) {
console.log('Fetching from cache');
return cache[n];
}
else {
console.log('Calculating result');
let result = fn(n);
cache[n] = result;
return result;
}
}
}
// создание функции с мемоизацией из чистой функции 'add'
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3)); // вычислено
console.log(memoizedAdd(3)); // взято из кэша
console.log(memoizedAdd(4)); // вычислено
console.log(memoizedAdd(4)); // взято из кэша
memoize
способна превращать другие функции в их эквиваленты с мемоизацией. Конечно, этот код не универсален, но его несложно переделать так, чтобы функция memoize
могла бы работать с функциями, имеющими любое количество аргументов._.memoize(func, [resolver])
@memoize
из decko.memoize
, или функции _.memoize
из Lodash, то, что получится, будет работать неправильно, так как рекурсивные функции вызывают сами себя, а не то, что получается после добавления возможностей по мемоизации. Как результат, переменная cache
в такой ситуации не выполняет своего назначения. Для того, чтобы решить эту проблему, рекурсивная функция должна вызывать свой вариант с мемоизацией. Вот как можно добавить мемоизацию в рекурсивную функцию вычисления факториала. Код, как обычно, можно найти на CodePen.// уже знакомая нам функция memoize
const memoize = (fn) => {
let cache = {};
return (...args) => {
let n = args[0];
if (n in cache) {
console.log('Fetching from cache', n);
return cache[n];
}
else {
console.log('Calculating result', n);
let result = fn(n);
cache[n] = result;
return result;
}
}
}
const factorial = memoize(
(x) => {
if (x === 0) {
return 1;
}
else {
return x * factorial(x - 1);
}
}
);
console.log(factorial(5)); // вычислено
console.log(factorial(6)); // вычислено для 6, но для предыдущих значений взято из кэша
factorial
рекурсивно вызывает свою версию с мемоизацией.factorial(5)
.К сожалению, не доступен сервер mySQL