Question 314801 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – how to store a vector as key of a map

I want to memoize the return result of my function that take two int. i know i could convert the vector as a string like 1-2 but is there another way to do it ?

I tried to set an array as a map but there is no comparison between array

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;
}
Tags:

2

Answers


  1. 0

    Updated:

    Guessing this is what you want:

    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;
}
    Origin:

    If you want to use array value as the key, you must keep the reference.

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

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

    map.get(key1); // works

    3

    map.get([1,2]);  // not work

    undefined

    Login or Signup to reply.
  2. 0

    To memoize the function gridTraveler without converting keys to strings, you can serialize the parameters as a unique object key.

    In JavaScript, objects or arrays used as keys in Maps are compared by their reference, not by their content MDN Documentation. Therefore, you need a method to generate a consistent, unique object reference for each pair of parameters.

    Here’s an approach keeping integers only:

    1. Use a nested map: The outer map keys are m, and each m maps to another map where the keys are n.

    2. Check and set values in this two-level map structure.

    Here’s how you can implement it:

    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;
}

    In this version, map is a map where each key is an m value, and each value is another map (let’s call it mMap). The mMap has keys of n and stores the results. This avoids the need for string conversion and keeps the benefits of memoization.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search