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

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

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

• 参数是对象。它们通常会字符串化为“[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

2. 参数是有逗号的字符串：

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

  将评估为

  false

  当已缓存的值是 falsy 值时，如 0、""、false。做

  if (params in cache)

  会避免这个问题

• params

  将被字符串化，这（如上所示）不能保证唯一标识一个参数数组。

改进

如果我们可以要求传递给我们的函数的参数是immutable，那么我们可以使用这些不可变的值或引用作为

Map

中的键。 当有多个参数时，这个 Map 将成为一个 Map 树，这样当在主 Map 中查找第一个参数时，它返回一个嵌套 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

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

Answer 2

这段代码有什么问题

function memoize(n){
     let cache={}
 return function (args){
  
  if(args in cache){
    console.log("cahce")
    return cache;
  }else{
      console.log("initial")
      cache[args]=n
    return cache;
  }
 }
}
const data=fetch("https://api.github.com/users/iamatulbansal").then(res=>res.json()).then(res=>res)

async function getData(data){
  //before caching
  let t=performance.now()
  const value=await data;
const result =memoize(value);
 result("user")
  console.log(performance.now()-t)


  //After caching
 let tt=performance.now()
result("user")
 console.log(performance.now()-tt)
  
}
getData(data)

Answer 3

对象键应该是字符串/符号。 根据输入数组如何影响输出，您可以

.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()

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