记忆化：参数可以用作缓存对象中的键吗？

Question

我有这个记忆功能的解决方案。

const slice = Array.prototype.slice
function memoize(fn){
    const cache = {}
    return (...args) => {
        const params = slice.call(args)
        console.log(params)
        if(cache[params]){
            console.log('cached')
            return cache[params]
        } else{
            let result = fn(...args)
            cache[params] = result
            console.log('not cached')
            return result
        }
    }
}

cache[params] 是重点。 cache 是一个对象，params 是一个数组。这会一直有效吗？经过一些研究，我仍然不确定这段代码是否正确。

Answer 1

对象键应该是 string/symbols。根据输入数组影响输出的方式，您可以 .join() 数组并将其用作缓存键：

const slice = Array.prototype.slice
function memoize(fn){
    const cache = {}
    return (...args) => {
        const params = slice.call(args)
        let paramsString = params.sort().join('');
        console.log(paramsString)
        if(cache[paramsString]){
            console.log('cached')
            return cache[paramsString]
        } else{
            let result = fn(...args)
            cache[paramsString] = result
            console.log('not cached')
            return result
        }
    }
}

如果顺序无关紧要，那么您可以 .sort()。如果顺序很重要，那么您可以删除排序并加入。这并不完美，但适用于简单的情况。

Answer 2

这种记忆可以用于非常简单的情况，但在许多其他情况下不起作用，例如：

参数是对象。它们通常会字符串化为“[object Object]”，因此不同的对象被视为相同。
参数是字符串但无法区分，因为当参数数组被字符串化（逗号分隔符）时，它们的分隔方式很差

一些失败的demo：

参数是对象

const slice = Array.prototype.slice

function memoize(fn){
    const cache = {}
    return (...args) => {
        const params = slice.call(args)
        if(cache[params]){
            return cache[params]
        } else{
            let result = fn(...args)
            cache[params] = result
            return result
        }
    }
}

// The function we will test with:
function sum(a) {
    let total = 0;
    for (let value of a) total += value;
    return total;
}

function test() {
    console.log(sum(new Set([1,2,3]))); // should be 6
    console.log(sum(new Set([2,4,6]))); // should be 12
}

console.log("Run test without memoization...");
test(); // Perform test without memoization
sum = memoize(sum); // Memoize the function
console.log("Run test WITH memoization...");
test(); // Test again, but now with memoization

参数是带有逗号的字符串：

const slice = Array.prototype.slice

function memoize(fn){
    const cache = {}
    return (...args) => {
        const params = slice.call(args)
        if(cache[params]){
            return cache[params]
        } else{
            let result = fn(...args)
            cache[params] = result
            return result
        }
    }
}

// The function we will test with:
function compareString(a, b) {
    return a.localeCompare(b); // returns -1, 0 or 1.
}

function test() {
    console.log(compareString("b,a", "c")); // should be -1
    // Change the arguments such that the concatenation with comma remains the same
    console.log(compareString("b", "a,c")); // should be  1
}

console.log("Run test without memoization...");
test(); // Perform test without memoization
compareString = memoize(compareString); // Memoize the function
console.log("Run test WITH memoization...");
test(); // Test again, but now with memoization

代码其他备注

调用slice是没用的，因为args已经是一个新数组了。
if(cache[params]) 当已经缓存的值是一个假值时，if(cache[params]) 将评估为 false，例如 0, "", false。做 if (params in cache) 会避免这个问题
params 将被字符串化，这（如上所示）不能保证唯一标识一个参数数组。

改进

如果我们可以要求传递给我们函数的参数是 不可变的，那么我们可以使用这些不可变的值或引用作为 Map 中的键。当有多个参数时，这个 Map 将成为一个 Map 树，因此当在主 Map 中查找第一个参数时，它 returns 一个嵌套 Map，然后在该 Map 中的下一个参数将是用作键等，直到为最后一个参数找到深度映射。在最终的 Map 中，保留键用于检索缓存的值。这个保留键可以是只有 memoize 函数知道的符号，这样它就永远不会与参数值发生冲突。

免责声明：当对象可以在调用之间发生变化时，这将不起作用。

外观如下：

function memoize(fn){
    const end = Symbol("end"); // A unique reference, only known here
    const cache = new Map;
    return (...args) => {
        let node = args.reduce((node, arg) => {
             if (!node.has(arg)) node.set(arg, new Map);
             return node.get(arg);
        }, cache);
        if (!node.has(end)) node.set(end, fn(...args));
        return node.get(end);
    }
}

// The function we will test with:
let numCalls = 0;
function length(a) { // Length of a linked list
    numCalls++; // Keep track of the number of calls made
    return a ? length(a.next) + 1 : 0;
}

function test() {
    numCalls = 0; // Reset the number of calls
    let head = { next: { next: { next: {}}}}; // Linked list with 4 nodes
    console.log(length(head)); // should be 4
    // Now exclude the head node:
    console.log(length(head.next)); // should be 3
    console.log("number of calls: ", numCalls); 
}

console.log("Run test without memoization...");
test(); // Perform test without memoization
length = memoize(length); // Memoize the function
console.log("Run test WITH memoization...");
test(); // Test again, but now with memoization

同样，当对象在调用之间发生变化时不能使用它。但对于所有其他情况，它应该可以正常工作。

记忆化：参数可以用作缓存对象中的键吗？

Memoization: can the arguments be used as key in the cache object?

javascript

arrays

object

memoization

代码其他备注

改进