如何创建一个 memoize 函数

Question

我被这个 memoize 问题难住了。我需要创建一个函数来检查是否已经为给定参数计算了一个值，return 先前的结果，或者运行计算和 return 该值。

虽然我是 JS 的新手，但我已经花了几个小时在这上面。我无法理解如何做到这一点。我不能使用任何内置函数，并且真的很想了解我需要做什么。

这就是我目前所知道的，这是错误的，在这一点上感觉像是伪代码。我已经在这里搜索了现有的 memoize 问题，但我似乎还无法找到任何解决方案。非常感谢任何帮助。

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

对不起，我应该更清楚。以下是我的具体要求： myMemoizeFunc 必须 return 一个函数，该函数将检查是否已经为给定的 arg 计算了计算，并且如果可能的话 return 该 val。 passedFunc 是一个保存计算结果的函数。我知道这可能看起来像是重复的，但我标记为不是这样，因为我在理解我应该在这里做什么时遇到了一些严重的困难，并且需要比其他帖子中提供的更多帮助。这就是我的思维过程让我走向的方向，但我又离题太远了。

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;
        }
    }
  }
};

我不应该在这里 returning i 或 passedFunc，但是在检查值时我还能在 if/else 中做什么？我已经关注这个问题很久了，我开始实现荒谬的代码并需要一些新的建议。

Answer 1

我认为这样做的主要技巧是创建一个对象，该对象存储之前作为键传入的参数，并将函数的结果作为值。

对于单个参数的记忆函数，我会这样实现：

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);
});

Answer 2

有许多可用的记忆库。有效地进行记忆并不像看起来那么简单。我建议使用图书馆。其中两个最快的是：

https://github.com/anywhichway/iMemoized

https://github.com/planttheidea/moize

Answer 3

请在此处查看全面的（-ish）记忆库列表：

Answer 4

将此视为上的扩展。

对于可变数量的参数，您可以使用类似这样的方法。

Note: This example is not optimal if you intent to pass complex arguments (arrays, objects, functions). Be sure to read further and not copy/paste blindly.

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 } 在 memoizedFn 调用之后没有被引用，所以通常会被垃圾回收。但是现在不可能了，因为 cache 仍然持有一个参考。它只能在 memoizedFn 本身被垃圾收集后被垃圾收集。

我首先展示了上面的内容，因为它展示了基本概念并以稍微简单的形式演示了缓存结构。要清理通常会被垃圾收集的缓存，我们应该对复杂对象使用 WeakMap 而不是 Map。

For those unfamiliar with WeakMap, the keys are a "weak" reference. This means that the keys do not count towards active references towards an object. Once an object is no longer referenced (not counting weak references) it will be garbage collected. This will in turn remove the key/value pair from the WeakMap instance.

const memo = (function () {
  const primitives = new Set([
    "undefined",
    "boolean",
    "number",
    "bigint",
    "string",
    "symbol"
  ]);
  
  function typeOf(item) {
    const type = typeof item;
    if (primitives.has(type)) return "primitive";
    return item === null ? "primitive" : "complex";
  }

  const map = {
    "primitive": Map,
    "complex": WeakMap
  };

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

    function get(args) {
      let node = cache;
      for (const arg of args) {
        const type = typeOf(arg);
        if (!(type in node)) node[type] = new map[type];
        if (!node[type].has(arg)) node[type].set(arg, {});
        node = node[type].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 fib = memo((n) => {
  console.log("fib called with", n);
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
});

// heavy operation with complex object
const heavyFn = memo((obj) => {
  console.log("heavyFn called with", obj);
  // heavy operation
  return obj.value * 2;
});

// multiple complex arguments
const map = memo((iterable, mapFn) => {
  console.log("map called with", iterable, mapFn);
  const result = [];
  for (const item of iterable) result.push(mapFn(item));
  return result;
});

console.log("### simple argument demonstration ###");
console.log("fib(3)", "//=>", fib(3));
console.log("fib(6)", "//=>", fib(6));
console.log("fib(5)", "//=>", fib(5));

console.log("### exlanation of when cache is garbage collected ###");
(function () {
  const item = { value: 7 };
  
  // item stays in memo cache until it is garbade collected
  console.log("heavyFn(item)", "//=>", heavyFn(item));
  console.log("heavyFn(item)", "//=>", heavyFn(item));
  
  // Does not use the cached item. Although the object has the same contents
  // it is a different instance, so not considdered the same.
  console.log("heavyFn({ value: 7 })", "//=>", heavyFn({ value: 7 }));
  // { value: 7 } is garbade collected (and removed from the memo cache)
})();
// item is garbade collected (and removed from memo cache) it is no longer in scope

console.log("### multiple complex arguments demonstration ###");
console.log("map([1], n => n * 2)", "//=>", map([1], n => n * 2));
// Does not use cache. Although the array and function have the same contents
// they are new instances, so not considdered the same.
console.log("map([1], n => n * 2)", "//=>", map([1], n => n * 2));

const ns = [1, 2];
const double = n => n * 2;
console.log("map(ns, double)", "//=>", map(ns, double));
// Does use cache, same instances are passed.
console.log("map(ns, double)", "//=>", map(ns, double));
// Does use cache, same instances are passed.
ns.push(3);
console.log("mutated ns", ns);
console.log("map(ns, double)", "//=>", map(ns, double));

结构基本保持不变，但根据参数的类型，它会在 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 key equality，参数被认为是相等的。如果您还需要记住抛出的任何错误，我希望这个答案为您提供了这样做的基石。

如何创建一个 memoize 函数

How to create a memoize function

javascript

underscore.js

memoization