Мемоизация (Кеш) (англ. memoization от англ. memory и англ. optimization) — пример использования кеша при разработке программного обеспечения, в программировании сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее:
- если не вызывалась, то функция вызывается, и результат её выполнения сохраняется;
- если вызывалась, то используется сохранённый результат.
Мемоизация может использоваться не только для увеличения скорости работы программы. Например, она используется при взаимно-рекурсивном нисходящем синтаксическом разборе в обобщённом алгоритме нисходящего синтаксического анализа.
Несмотря на связь с кешированием, мемоизация является особым видом оптимизации, отличающимся от таких способов кеширования, как буферизация и подмена страниц.
В рамках языков логического программирования мемоизация известна под названием «табулирования».
Примеры использования
Приведенная ниже функция memoize() сохраняет результаты каждого вызова принимаемой функции в виде [ключ:значение].
// Функция, генерирующая ключ исходя из параметров const generateKey = args => ( args.map(x => `${x.toString()}:${typeof(x)}`).join('|') // Результат: "x1:number|x2:number|..." ); // Принимает функцию в качестве параметра const memoize = fn => { const cache = {}; return (...args) => { // Генерирует ключ для сохранения результата const key = generateKey(args); const val = cache[key]; // Проверяет, существует по данному ключу какое-либо значение и возвращает его, если оно есть if (val) return val; // Сохраняет результат вызова функции const res = fn(...args); cache[key] = res; // Возвращает результат return res; }; };С помощью нее мы можем избежать повторного выполнения вычислений в случае, если они уже были произведены.
// Функция, находящая сумму чисел от a до b const sumSeq = (a, b) => { console.log('Calculate sum'); let r = 0; for (let i = a; i < b; i++) r += i; return r; }; // Производим мемоизацию функции sumSeq const mSumSeq = memoize(sumSeq); console.log('First call mSumSeq(2, 5)'); console.log('Value: ' + mSumSeq(2, 5)); // Выводит в консоль "9" console.log('Second call mSumSeq(2, 5)'); console.log('From cache: ' + mSumSeq(2, 5)); // Выводит в консоль "9" console.log('Call mSumSeq(2, 6)'); console.log('Calculated: ' + mSumSeq(2, 6)); // Выводит в консоль "14"При повторном вызове функции mSumSeq( 2, 5 ) программа не выполняла повторные вычисления суммы, она проверила наличие значения по ключу [2:number|5:number] в кеше, и, поскольку он уже был создан и ему было присвоено значение 9 при первом вызове функции, это значение передастся переменной val из memoize() и возвратится в качестве аргумента в console.log().
Данный пример показывает самое простое применение мемоизации в программировании, поэтому особых изменений в скорости работы можно не заметить, однако этот способ оптимизации может сильно облегчить работу процессора при нагруженных математических вычислениях.