代码之家 › 专栏 › 技术社区 › Armeen Moon

memoize函数可以使用ES6映射还是哈希表?

memoization hashtable ecmascript-6 dictionary javascript

Armeen Moon · 技术社区 · 7 年前

前言: 努力学习 ES6 Maps 通过转换利用哈希表的简单备忘录。

问题:

起始对象是否可以替换为 new Map() 如果是,如何?有什么好处吗?若否,原因为何?

描述:

这是一个具有功能的备忘录( add )和起始对象( {} ). 应召 记忆添加 ( mAdd )参数如下: spread 最后,测试/设置哈希索引并返回值。

LINK TO CODE

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

2 回复 | 直到 7 年前

Me.Name 7 年前

主要问题是参数不代表同一对象。它们的内容确实如此,这就是为什么严格化会起作用。

使用对象作为散列,还执行一种字符串化:属性 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;
};

可以通过多种方式创建密钥。严格化是可能的,甚至可能 const key = uneval(a); 可以根据长度和内容创建某种散列整数,但其可靠性取决于可能的内容。e、 g.如果已知值从不超过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));

Ara Yeressian 7 年前

问题在于,映射使用对象的引用来标识为键(如果提供的键是对象而不是基元类型)。在这种情况下一

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

一变量

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

注意:您的代码根本不可读。所以我不得不对它稍加编辑,使它更容易理解。