memoize 函数可以使用 ES6 Map 还是哈希表?
Can a memoize function use a ES6 Map vs a hashtable?
前言: 尝试通过转换利用哈希 table 的简单记忆来学习 ES6 Maps。
问题:
是否可以将起始对象替换为 new Map()
,如果可以,如何替换?有什么好处吗?如果不是,为什么?
描述:
这是一个带有函数 (add
) 和起始对象 ({}
) 的备忘录。在调用 memoized add (mAdd
) 时,参数为 spread。最后hash索引为tested/sets,返回值
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));
问题是 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));
注意:您的代码根本不可读。所以我不得不对其进行一些编辑以使其更易于理解。
主要问题是参数不代表同一个对象。他们的内容确实如此,这就是为什么字符串化会起作用的原因。
使用对象作为散列,也执行一种字符串化:创建 属性 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
returns 地图对象本身,而不是正在使用的值设置).
最简单的实现是将键字符串化。最安全的是 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 key =createKey(a);
调用 const createKey = ([a1,...a]) => a.length ? a1 + 100 * createKey(a) : a1;
的助手
当然,对于示例,直接添加总是比创建密钥和查找密钥更快,但对于一般用途,创建密钥的方法是决定性因素。
我意识到我可能不是在说所有这些新东西,但最重要的是传递的参数并不代表同一个对象。也就是说,我想建议另一种选择:创建一个分支地图。包含子映射(以第一个参数为键)到结果(以第二个参数为键)或后续映射到第二个元素的基本映射。
edit 上述分支的一个例子(单个map可以用于不同的功能以减少内存占用):
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));
前言: 尝试通过转换利用哈希 table 的简单记忆来学习 ES6 Maps。
问题:
是否可以将起始对象替换为 new Map()
,如果可以,如何替换?有什么好处吗?如果不是,为什么?
描述:
这是一个带有函数 (add
) 和起始对象 ({}
) 的备忘录。在调用 memoized add (mAdd
) 时,参数为 spread。最后hash索引为tested/sets,返回值
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));
问题是 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));
注意:您的代码根本不可读。所以我不得不对其进行一些编辑以使其更易于理解。
主要问题是参数不代表同一个对象。他们的内容确实如此,这就是为什么字符串化会起作用的原因。
使用对象作为散列,也执行一种字符串化:创建 属性 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
returns 地图对象本身,而不是正在使用的值设置).
最简单的实现是将键字符串化。最安全的是 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 key =createKey(a);
const createKey = ([a1,...a]) => a.length ? a1 + 100 * createKey(a) : a1;
的助手
当然,对于示例,直接添加总是比创建密钥和查找密钥更快,但对于一般用途,创建密钥的方法是决定性因素。
我意识到我可能不是在说所有这些新东西,但最重要的是传递的参数并不代表同一个对象。也就是说,我想建议另一种选择:创建一个分支地图。包含子映射(以第一个参数为键)到结果(以第二个参数为键)或后续映射到第二个元素的基本映射。
edit 上述分支的一个例子(单个map可以用于不同的功能以减少内存占用):
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));