WikiSort.ru - Программирование

Мемоизация (запоминание, от англ. memoization (англ.) в программировании) — сохранение результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ. Перед вызовом функции проверяется, вызывалась ли функция ранее:

• если не вызывалась, функция вызывается и результат её выполнения сохраняется;
• если вызывалась, используется сохранённый результат.

Мемоизация может использоваться не только для увеличения скорости работы программы. Например, она используется при простом взаимно-рекурсивном нисходящем синтаксическом разборе в обобщённом алгоритме нисходящего синтаксического анализа^[1].

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

В рамках языков логического программирования мемоизация известна под названием «табулирования».

Примеры использования

Приведенная ниже функция 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().

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

См. также

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

Ссылки

Примеры кода взяты из источника:

HowProgrammingWorks, Тимур Шемсединов - Github репозиторий.

Примечания

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.

В другом языковом разделе есть более полная статья Memoization (англ.). Вы можете помочь проекту, расширив текущую статью с помощью перевода. При этом, для соблюдения правил атрибуции, следует установить шаблон {{переведённая статья}} на страницу обсуждения, либо указать ссылку на статью-источник в комментарии к правке.

Это заготовка статьи о программировании. Вы можете помочь проекту, дополнив её.