如何将向量作为映射的键存储？

Question

我想为我的接受两个整数作为参数的函数的结果进行记忆化。我知道我可以将向量转换为字符串形式，例如“1-2”，但是否有其他方法可以实现呢？

我尝试使用一个数组作为映射（Map）的键，但由于没有数组之间的比较方法，这种方法行不通。

let map = new Map();

function gridTraveler(m, n){
    if (m === 0 || n === 0)
        return 0;
    if (m === 1 && n === 1)
        return 1;
    if (map.has([m,n])) // 这里尝试用数组作为键，但无法有效工作
        return map.get([m, n]);
    let res = gridTraveler(m-1, n) + gridTraveler(m, n-1);
    map.set([m, n], res);
    return res;
}

为了有效地在Map中存储数组作为键，你可以将数组转化为一个字符串，例如m-n，或者创建一个唯一的标识符来代表输入的二维坐标：

let map = new Map();

function gridTraveler(m, n){
    const key = `${m},${n}`;
    
    if (m === 0 || n === 0)
        return 0;
    if (m === 1 && n === 1)
        return 1;
    if (map.has(key))
        return map.get(key);
    let res = gridTraveler(m-1, n) + gridTraveler(m, n-1);
    map.set(key, res);
    return res;
}

Tom Lehman · Answer

猜测您想要的是这样的代码：

function hashKey(m, n) {
  return [m, n].sort().join();
}

let map = new Map();

function gridTraveler(m, n) {
  if (m === 0 || n === 0) return 0;
  if (m === 1 && n === 1) return 1;

  const key = hashKey(m, n);
  if (map.has(key)) return map.get(key);

  let res = gridTraveler(m - 1, n) + gridTraveler(m, n - 1);
  map.set(key, res);

  return res;
}

原问题：

如果你想使用数组作为Map的键值，你必须保持引用的一致性。

const map = new Map();
const key1 = [1,2];
map.set(key1, 3);

此时Map结构为：

Map(1) {Array(2) => 3}

map.get(key1); // 此处有效，因为key1与设置时的引用一致

返回结果：

map.get([1,2]);  // 此处无效，尽管内容相同，但引用不同

返回结果：

undefined

Ken White · Answer

要实现对函数gridTraveler的记忆化而不将键转换为字符串，你可以将参数序列化为一个唯一的对象键。

在JavaScript中，当在Map中使用对象或数组作为键时，它们是通过引用而非内容来进行比较的（参见MDN文档）。因此，你需要一种方法为每一对参数生成一个一致且唯一的对象引用。

以下是一个仅保留整数的方法：

使用嵌套Map：外层Map的键为 m，每个 m 映射到另一个其键为 n 的Map。
在这个双层Map结构中检查并设置值。

以下是实现方式：

let map = new Map();

function gridTraveler(m, n) {
    if (m === 0 || n === 0) return 0;
    if (m === 1 && n === 1) return 1;

    if (!map.has(m)) map.set(m, new Map());
    const mMap = map.get(m);

    if (mMap.has(n)) return mMap.get(n);

    let res = gridTraveler(m - 1, n) + gridTraveler(m, n - 1);
    mMap.set(n, res);
    return res;
}

在这个版本中，map 是一个Map，其中每个键是一个 m 值，每个值又是另一个Map（我们称为 mMap）。这个 mMap 具有 n 作为键，并存储结果。这样就避免了字符串转换的需求，同时保持了记忆化的优势。