Как создать функцию памятки

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

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

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

  myMemoizeFunc = function(passedFunc) {
  var firstRun = passedFunc;
  function check(passedFunc){
    if(firstRun === undefined){
        return passedFunc;
    }else{return firstRun;}
  }
  };

Извините, мне следовало быть более ясным. Вот мои конкретные требования: myMemoizeFunc должен вернуть функцию, которая проверит, был ли расчет уже рассчитан для данного аргумента, и вернет этот val, если это возможно. Переданный параметр является функцией, которая содержит результат вычисления. Я понимаю, что это может показаться дубликатом, но я отмечаю, что это не так, поскольку у меня возникли серьезные трудности с пониманием того, что я должен делать здесь, и мне нужна дополнительная помощь, чем указано в других сообщениях. Это то, к чему меня ведет мой мыслительный процесс, но опять же, я далеко.

myMemoizeFunc = function(passedFunc) {
var allValues = [];
return function(){
    for(var i = 0; i < myValues.length; i++){
        if(myValues[i] === passedFunc){
            return i;
        }
        else{
            myValues.push(passedFunc);
            return passedFunc;
        }
    }
  }
};

Я не должен возвращать i или passFunc здесь, но что еще я могу сделать в if / else при проверке значения? Я так долго смотрю на эту проблему, я начинаю реализовывать смешной код, который нуждается в свежих советах.

Источник

5 ответов

Решение

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

Для запоминания функций одного аргумента я бы реализовал это так:

var myMemoizeFunc = function (passedFunc) {
    var cache = {};
    return function (x) {
        if (x in cache) return cache[x];
        return cache[x] = passedFunc(x);
    };
};

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

var factorial = myMemoizeFunc(function(n) {
    if(n < 2) return 1;
    return n * factorial(n-1);
});
Источник

Считайте это продолжением ответа Питера Олсона .

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

Примечание. Этот пример не является оптимальным, если вы собираетесь передавать сложные аргументы (массивы, объекты, функции). Обязательно читайте дальше, а не копируйте / вставляйте вслепую.

      function memo(fn) {
  const cache = {};

  function get(args) {
    let node = cache;
    for (const arg of args) {
      if (!("next" in node)) node.next = new Map();
      if (!node.next.has(arg)) node.next.set(arg, {});
      node = node.next.get(arg);
    }
    return node;
  }
  
  return function (...args) {
    const cache = get(args);
    if ("item" in cache) return cache.item;
    cache.item = fn(...args);
    return cache.item;
  }
}

Это строит следующую древовидную структуру кеша:

      const memoizedFn = memo(fn);
memoizedFn();
memoizedFn(1);
memoizedFn(1, 2);
memoizedFn(2, 1);

cache = {
  item: fn(),
  next: Map{ // <- Map contents depicted as object
    1: {
      item: fn(1),
      next: Map{
        2: { item: fn(1, 2) }
      }
    },
    2: {
      next: Map{
        1: { item: fn(2, 1) }
      }
    }
  }
}

Это решение приводит к утечке памяти при передаче сложных аргументов (массивов, объектов, функций), на которые впоследствии больше не ссылаются.

      memoizedFn({ a: 1 })

Потому что { a: 1 }не упоминается после вызова, это обычно будет сборщиком мусора. Однако сейчас этого не может быть, потому что cacheвсе еще есть ссылка. Сборщик мусора может быть произведен только один раз. memoizedFn сам по себе является сборщиком мусора.

Я показал это первым, потому что оно показывает базовую концепцию и демонстрирует структуру кеша в несколько простой форме. Чтобы очистить кеш, который обычно собирался сборщиком мусора, мы должны использовать вместо a для сложных объектов.

Для тех, кто с ними не знаком, клавиши являются «слабым» ориентиром. Это означает, что ключи не учитываются в активных ссылках на объект. Когда на объект больше не ссылаются (не считая слабых ссылок), он будет удален сборщиком мусора. Это, в свою очередь, удалит пару ключ / значение из WeakMap пример.

Структура остается практически такой же, но в зависимости от типа аргумента она будет выглядеть либо в primitive: Map{} или complex: WeakMap{} объект.

      const memoizedFn = memo(fn);
memoizedFn();
memoizedFn(1);
memoizedFn(1, 2);
memoizedFn({ value: 2 }, 1);

cache = {
  item: fn(),
  primitive: Map{
    1: {
      item: fn(1),
      primitive: Map{
        2: { item: fn(1, 2) }
      }
    }
  },
  complex: WeakMap{
    { value: 2 }: { // <- cleared if { value: 2 } is garbage collected
      primitive: Map{
        1: { item: fn({ value: 2 }, 1) }
      }
    }
  }
}

Это решение не запоминает возникшие ошибки. Аргументы считаются равными на основании Mapключевое равенство . Если вам также нужно запомнить любые возникшие ошибки, я надеюсь, что этот ответ дал вам строительные блоки для этого.

Источник

Есть несколько доступных библиотек памятки. Эффективное запоминание не так просто, как кажется. Я предлагаю использовать библиотеку. Два из самых быстрых:

https://github.com/anywhichway/iMemoized

https://github.com/planttheidea/moize

Источник

См. Здесь полный (-ish) список библиотек мемоизации: /questions/54711653/kakie-biblioteki-memoizatsii-dostupnyi-dlya-javascript/54711658#54711658

Источник

Эта версия верна для любой ситуации (несколько аргументов)

      const memorized = (fn) => {
  let cache = {}
  const makeKey = (...args) => {
    return args.map((o) => JSON.stringify(o)).join('_')
  }

  return function (...args) {
    const key = makeKey(args)

    if (cache[key]) {     
      console.log('return from cache')   
      return cache[key]
    } else {
      console.log('calculating')
      const newValue = fn(...args)
      cache[key] = newValue
      return newValue
    }
  }
}
const sum = (a, b, c)=> a + b + c
const square = a => a*a
const sumMemorized = memorized(sum)
const squareMemorized = memorized(square)
sumMemorized(1,2,3)
sumMemorized(1,2,3)
sumMemorized(1,2,3)
sumMemorized(1,2,3)
sumMemorized(1,2,3)
squareMemorized(2)
squareMemorized(3)
Источник
Другие вопросы по тегам