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

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

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

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 是一个数组。这会一直有效吗?经过一些研究,我仍然不确定这段代码是否正确。

对象键应该是 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()。如果顺序很重要,那么您可以删除排序并加入。这并不完美,但适用于简单的情况。

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

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

一些失败的demo:

  1. 参数是对象

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

  1. 参数是带有逗号的字符串:

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

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