WTF - это мемоизация

Хорошо, те, кто увидел этот термин впервые в своей жизни, могут трепетать перед этим новым термином (как и я), бормоча: «Ух ты, еще одна причудливая техника в мире информатики, которую я должен изучить? ”

Однако это неправда. На самом деле это самый известный метод, который мы когда-либо знали - Кэширование!

В мире информатики кеширование есть повсюду. От оборудования до программного обеспечения кэширование существует почти на каждом уровне (физическом или абстракционном). Например, кеш L1, L2, L3 в ЦП, буфер базы данных (буферный пул InnoDB в MySQL), локальный кеш в браузере (например, локальное хранилище, IndexDB), управление кешем HTTP и т. Д.

Все цели кэширования одинаковы - Избегайте многократного выполнения одной и той же работы, чтобы не тратить ненужное время или ресурсы! Потому что мы, ребята из информатики, «ленивы», мы не хотим повторять одни и те же дорогостоящие работы. Это глупо! Мы предпочли бы обменять некоторое пространство (память или диск) на более быстрый и эффективный запуск кода.

Для мемоизации это просто метод кеширования в рамках функции!

Из Википедии определение мемоизации:

В вычислениях мемоизация или мемоизация - это метод оптимизации, используемый в первую очередь для ускорения компьютерных программ путем сохранения результатов дорогостоящих вызовов функции f и возврата кэшированного результата, когда тот же самый входы повторяются снова.

Звучит довольно просто, правда? Мы просто возвращаем кешированный результат, если вызываем функцию с теми же параметрами без пересчета (но требуется, чтобы функция была чистой функцией). Хорошо, код подсказывает, давайте посмотрим на реальных примерах.

Мемоизация - это способ снизить время стоимость функции в обмен на место.

ПРИМЕЧАНИЕ. Следующие примеры будут написаны на Javascript.

Фиктивный пример

const dummyLookup = {};
function dummy(a, b, c) {
    const key = `${a}-${b}-${c}`;
    if (key in dummyLookup) {
        return dummyLookup[key];
    }
   
    const result = a + b + c;
    dummyLookup[key] = result;
    return result;
}

Как видите, мы преобразуем параметры dummy в строку и объединяем их в качестве ключа таблицы поиска. Скажем, если мы вызываем 10000 раз dummy(1, 2, 3), реальное вычисление происходит только в первый раз, остальные 9999 вызовов просто возвращают кешированное значение в dummyLookup, БЫСТРО!

Легко, да? Но я знаю, что вам не нравится dummyLookup, который определен вне dummy.

Похоже, мы можем превратить любую чистую функцию в мемоизированную версию? Да! Точно! Почему у нас нет вспомогательной функции, чтобы сделать это за нас, чтобы не писать шаблонный код таблицы поиска?

Итак, давайте напишем функцию более высокого порядка, чтобы возвращать запомненную версию любой чистой функции!

ПРИМЕЧАНИЕ. Приведенный ниже пример работает только в том случае, если все аргументы функции f имеют разные строковые представления.

function memoize(f) {
    const cacheLookup = {}; // Value cache stored in the closure
    return function() {
        const key = Array.prototype.join.call(arguments,'-');
        if (key in cacheLookup) {
            return cacheLookup[key];
        } else {
            return cacheLookup[key] = f.apply(this, arguments);
        }
    }
}

Итак, давайте используем memoize, чтобы вернуть запомненный dummy!

function dummy(a, b, c) {
    console.log('computing...');
    return a + b + c;
}
const memoizedDummy = memoize(dummy);
memoizedDummy(1, 2, 3);   // 6 is returned and 'computing' is printed
memoizedDummy(1, 2, 3);   // 6 is returned but nothing is printed!

Случаи применения

На данный момент мы можем легко придумать 2 варианта использования, чтобы превратить функцию в ее мемоизированную версию.

1. Если функция чистая, требует больших вычислений и вызывается повторно
2. Если функция чистая и рекурсивная

Первый простой, это просто кеширование.
Второй более интересный и что-то напоминает нам ……

Динамическое программирование!

Пример Фибоначчи

Мы можем написать рекурсивную функцию для быстрого получения числа Фибоначчи.

function fibonacci(n) {
    if ((n === 0) || (n === 1)) {
        return n;
    }
    return (fibonacci(n - 1) + fibonacci(n - 2));
}

Код такой чистый, такой аккуратный и такой красивый, правда;)? Однако его сложность O (2 ^ n), плохо ... Если мы разберем выполнение кода на следующий график (возьмем n = 6)

Мы можем заметить, что есть несколько повторяющихся вычислений. Например, fibonacci(3) вычисляется 3 раза! Если мы сделаем fibonacci мемоизированным, то мы можем гарантировать, что для числа n это число Фибоначчи будет вычислено только один раз.

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

const fibonacci = memoize(function (n) {
    if ((n === 0) || (n === 1)) {
        return n;
    }
    return (fibonacci(n - 1) + fibonacci(n - 2));
});

Как вы можете видеть на графике ниже, значения в синих полях - это значения, которые уже были рассчитаны, и поэтому вызовы можно пропустить. И вуаля! Теперь сложность превращается в O (n)! (Однако пространство также становится O (n))

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

Динамическое программирование

Как упоминалось ранее, мемоизация напоминает динамическое программирование. Хотя DP обычно использует подход снизу вверх и сохраняет результаты подзадач в таблице массива, в то время как мемоизация использует подход сверху вниз и сохраняет результаты в хеш-коде. стол. По сути, они разделяют одну и ту же идею, или мы можем сказать, что это одно и то же - все они сохраняют результаты подзадач в памяти и пропускают пересчет этих подзадач, если их ответы уже находятся в памяти.

Так в чем разница?

• Сверху вниз и снизу вверх
  DP решает проблему «снизу вверх», сначала решая все связанные подзадачи, обычно путем заполнения n-мерной таблицы. Затем на основе результатов в таблице вычисляется решение исходной задачи. Так как это «снизу вверх», оно решит все подзадачи, даже если они могут не понадобиться главной проблеме.
  Мемоизация решает проблему «сверху вниз», поддерживая карта уже решенных подзадач. Сначала он решает «верхнюю» проблему, которая обычно возвращается для решения подзадач. Поскольку это метод «сверху вниз», он решит только необходимые подзадачи.
• Рекурсивный и итеративный
  DP является итеративным (с использованием циклов), то есть у него нет недостатка, который имеет Memoization - накладные расходы на рекурсию и фатальные Maximum call stack size exceeded проблема.

Пример применения

Пришло время увидеть примеры из реального мира.

Reselect - Селекторная библиотека для Redux

Чтобы подключить React к Redux, люди обычно используют привязку response-redux. Эта библиотека предоставляет API mapStateToProps для передачи состояния, которое живет в мире Redux, в мир React.

В следующем примере со страницы повторного выбора на Github мы видим, что каждый раз при обновлении дерева состояний getVisibleTodos будет вызываться один раз. Если дерево состояний велико или вычисления дороги, повторение вычислений при каждом обновлении может вызвать проблемы с производительностью.

const mapStateToProps = (state) => {
  return {
    todos: getVisibleTodos(state.todos, state.visibilityFilter)
  }
}

Поэтому повторный выбор помогает избежать этих ненужных перерасчетов, создавая «мемоизированный» селектор. Он пересчитывает todos, когда значение state.todos или state.visibilityFilter изменяется, но не когда изменения происходят в других (несвязанных) частях дерева состояний.

Reselect предоставляет функцию createSelector для создания мемоизированных селекторов. createSelector принимает в качестве аргументов массив селекторов ввода и функцию преобразования. Если дерево состояний Redux изменено таким образом, что вызывает изменение значения селектора ввода, селектор вызовет свою функцию преобразования со значениями селекторов ввода в качестве аргументов и вернет результат. Если значения селекторов ввода такие же, как и при предыдущем вызове селектора, он вернет ранее вычисленное значение вместо вызова функции преобразования.

Следующий код является примером использования, последняя функция - это функция преобразования для вычисления окончательного результата, а предыдущие функции - это функции выбора.

const getVisibleTodosFilteredByKeyword = createSelector(
  [ getVisibleTodos, getKeyword ],
  (visibleTodos, keyword) => visibleTodos.filter(
    todo => todo.text.includes(keyword)
  )
)

Так где же живет мемоизация? Давайте погрузимся в исходный код повторного выбора (на самом деле исходный код составляет всего около 100 строк кода!). Способ создания функции memoized аналогичен нашей версии.

function defaultMemoize(func, equalityCheck = defaultEqualityCheck) {
  let lastArgs = null
  let lastResult = null
  // we reference arguments instead of spreading them for performance reasons
  return function () {
    if (!areArgumentsShallowlyEqual(equalityCheck, lastArgs, arguments)) {
      // apply arguments instead of spreading for performance.
      lastResult = func.apply(null, arguments)
    }
    lastArgs = arguments
    return lastResult
  }
}

defaultMemoize также является функцией более высокого порядка для возврата мемоизированной функции, но вместо поддержки карты она сохраняет последние аргументы в lastArgs, что означает, что она может «запомнить» только один последний результат. Обернутая функция будет вызвана только в том случае, если текущие аргументы отличаются от lastArgs путем проверки areArgumentsShallowlyEqual.

areArgumnetsShallowlyEqual просто проверяет, все ли предыдущие аргументы и следующие аргументы строго равны (===).

function areArgumentsShallowlyEqual(equalityCheck, prev, next) {
  if (prev === null || next === null || prev.length !== next.length) {
    return false
  }
  // Do this in a for loop (and not a `forEach` or an `every`) so we     can determine equality as fast as possible.
  const length = prev.length
  for (let i = 0; i < length; i++) {
    if (!equalityCheck(prev[i], next[i])) {
      return false
    }
  }
  return true
}

Если еще раз взглянуть на createSelector([...selectors], trasnformFunction) API, то повторное выделение просто делает trasnformFunction мемоизованным! Выход selectors будет входом transformFunction, и если все входы такие же, как и при последнем вызове, transformFunction просто вернет кэшированный результат без «вычисления» входов.

Заключение

Мемоизация - это метод кэширования результатов функции «в» самой функции, чтобы функция имела память, и вызывающим абонентам не нужно знать, является ли функция мемоизированный или нет. Если функция вызывается с теми же аргументами, что и раньше (вы можете определить, насколько велика память функции), ей просто нужно вернуть кешированный результат, фактически не выполняя вычисления. Хотя мы можем буквально сделать любую чистую функцию мемоизируемой, нам следует подумать об этом только для тех, возможно, часто вызываемых функций, аргументы которых могут повторяться постоянно.