一个memoize函数可以使用ES6 Map而不是哈希表吗？

Question

前言：试图通过将一个利用哈希表的简单记忆化函数转换为ES6 Maps来学习ES6 Maps。

问题：

可以用new Map()替换起始对象吗？如果可以，如何操作？有什么优点？如果不行，为什么？

---

描述：

这里有一个记忆化函数，它接受一个函数(add)和一个起始对象({})。在调用记忆化 add(mAdd)时，参数会被展开。最后，测试/设置哈希索引并返回值。

代码链接

const memo = (fn, hash) => (...a) => {
  return hash[a] === void 0 ?  hash[a] = fn(...a) : `${hash[a]} memo`;
};

const add = (x, y) =>  x + y;

const mAdd = memo(add, {});


console.log(mAdd(2,2));
console.log(mAdd(2,2));

地图不可用：

const memo = (fn, map) => (...a) => {
  return map.get(a) === void 0 ?  map.set(a, fn(...a)) : `${map.get(a)} memo`;
};

const add = (x, y) =>  x + y;

const mAdd = memo(add, new Map());


console.log(mAdd(2,2));
console.log(mAdd(2,2));

- Armeen Moon

---

if so, how? - replace {} with new Map() - Jaromanda X

@JaromandaX 这不是那么容易吗？https://repl.it/E9DG/1 我已经尝试过了。 - Armeen Moon

我也是这样做的，而且奇怪的是它对我起作用了。 - Jaromanda X

你可能也想为此查看WeakMaps。 - MarcoL

你能否提供一个答案吗？我仍然不确定标记为正确的问题是否是最佳答案。 - Armeen Moon

Answer 1

主要问题在于参数并不代表同一个对象，尽管它们的内容相同，这就是为什么字符串化会起作用的原因。

使用对象作为哈希时，也执行了一种串行化：创建了一个属性2,2。(顺便说一句: 这不是完整的证明，因为内容被扁平化了。参数[1,[2,3]]和[1,2,3]都将创建属性[1,2,3])

然而，由于Map实际上更智能，对象本身被用作键，对于每次调用，新对象被创建来表示参数。

使用相同的参数进行调用将有效，但当然这会使函数变得不太有用：

var pars = [2,2];
console.log(mAdd(pars));
console.log(mAdd(pars));

（方法签名需要更改为const memo = (fn, map) => (a) => {才能使上述内容起作用。还请注意，Map.set返回的是映射对象本身，而不是正在设置的值。）

最简单的实现方法是将键序列化为字符串。最安全的方法是使用JSON.stringify处理所有情况，但如果您相对确定内容，可以使用join等方法：

const memo = (fn, map) => (...a) => {
    const key = a.join(',');
  if(map.has(key))
        return `${map.get(key)} memo`;
    let res = fn(...a);
  map.set(key, res );
  return res;
};

创建密钥有几种方式。可以使用stringify，甚至可以使用const key = uneval(a);。可以基于长度和内容创建某种哈希整数，但其可靠性取决于可能的内容。例如，如果已知值从不超过100且参数数量不是太长，则可以使用一个助手const createKey = ([a1,...a]) => a.length ? a1 + 100 * createKey(a) : a1;调用，并使用const key =createKey(a);。

当然，对于这个例子，直接添加总是比创建密钥和查找密钥更快，但对于一般情况，创建密钥的方法是决定性的因素。

我意识到在所有这些中，我可能没有说出新的东西，但最重要的是传递的参数不表示相同的对象。也就是说，我想提出另一种选择：创建分支映射。基本映射包含子映射（以第一个参数为键），指向结果（以第二个参数为键）或后续映射到第二个元素。 编辑 下面是所述分支的示例（单个映射可用于不同函数以减少内存占用）：

const memoMap = new Map(); //use a general map for branches for all memoized functions, because result is stored in the child function as the key

const memo = (fn) => (...a) => {
  let key, r = a, map = memoMap;
  while(r.length){
      [key,...r] = r;      
      if(map.has(key))
       map = map.get(key);
      else
       map.set(key, map = new Map());
  }
  let res = map.get(fn); //get result for this specific function
  if(res===undefined)
   map.set(fn, res = fn(...a));
  else return `${res} memo`; //<-- line for testing purposes
  return res;
};


const add = (x, y) =>  x + y,
  subtr = (x,y) => x - y,
  mAdd = memo(add);

console.log(mAdd(2,2));
console.log(mAdd(2,2));
console.log(memo(subtr)(2,2));
console.log(memo(subtr)(2,2));

- Me.Name

Answer 2

问题在于Map使用对象的引用作为键来识别（如果提供的键是对象而不是原始类型）。 在这种情况下，a变量是一个数组，即使每次调用它都具有相同的值，但该变量的引用不同，因此Map将其视为新键。 请查看底部代码。

const test = new Map();
const a = ['bla'];
test.set(a, 'b');
console.log(test.get(a));
const f = ['bla'];
console.log(test.get(f));

一个解决此问题的方法是将a变量转换为字符串。

const memo = (fn, hash) => (...a) => {
  const key = JSON.stringify(a);
  if (hash.has(key)) {
    return `${hash.get(key)} memo`;        
  }
  const val = fn(...a);
  hash.set(key, val);
  return val;
};

const add = (x, y) =>  x + y;

const mAdd = memo(add, new Map());


console.log(mAdd(2,2));
console.log(mAdd(2,2));

注意：你的代码完全不易读。所以我必须稍微编辑一下，让它更容易理解。

- Ara Yeressian

---

我缺少的是密钥创建和.has方法！谢谢你提供的参考资料！ - Armeen Moon

可以。_"Objects can't be used as key in Map"_的说法是错误的。 - a better oliver

@zeroflagL 你有更好的回答吗？我真的不喜欢将参数字符串化以创建键。 - Armeen Moon

@zeroflagL是正确的。Matthew Harwood请看一下我更新的帖子。 - Ara Yeressian

如果您不想将参数字符串化以创建键，则可以替换传递的对象中的唯一属性，而不是使用对象本身，例如{uid：“123”，name：“joe”}，您将使用“123”。即使对于基元，也通过连接一堆字符串来创建总体键也非常缓慢。请参见iMemoized，其中提供了使用常规JavaScript对象作为缓存的索引式记忆化的示例。 - AnyWhichWay