Map vs Object Time complexity (Node.js)

Question

Considering those Code Solutions written in Node.js (see https://adventofcode.com/2020/day/15)

The first Snippet uses a Map for storing and accessing Data. It takes around 19 seconds in Visual Code debugger on my local machine, until the solution is printed. The second algorithm is using Object instead of Map and simply won't end. You can check it out.

What is the reason, the runtime of the second algorithm using Object is so much different and simply won't finish? They are using exactly the same code, one uses Map, the other uses Object.

Here is the Map example:

//const input = "0,3,6" // the 30000000th number spoken is 175594.
const input = '0,13,16,17,1,10,6';
const spoken = input.split(",").map(char => parseInt(char, 10));
const mem = new Map();

for (let n = 0; n < spoken.length; n++) {
  const num = spoken[n];
  if (!mem.has(num)) {
    mem.set(num, []);
  }
  mem.get(num).push(n);
}

for (let n = spoken.length; n < 30000000; n++) {
  let last = spoken[n - 1],
    next;

  if (mem.has(last) && mem.get(last).length > 1) {
    const turns = mem.get(last);
    next = turns[turns.length - 1] - turns[turns.length - 2];
  } else {
    next = -1;
  }

  if (next === -1) {
    spoken.push(0);
    if (!mem.has(0)) {
      mem.set(0, [n]);
    } else {
      mem.get(0).push(n);
    }
    continue;
  }

  spoken.push(next);

  if (!mem.has(next)) {
    mem.set(next, [n]);
  } else {
    mem.get(next).push(n);
  }
}

console.log(spoken[spoken.length - 1]) // 31916

Now, instead of Map, Object is used here:

//const input = "0,3,6" // the 30000000th number spoken is 175594.
const input = '0,13,16,17,1,10,6';
const spoken = input.split(",").map(char => parseInt(char, 10));
const mem = {};

for (let n = 0; n < spoken.length; n++) {
  const num = spoken[n];
  if (!mem[num]) {
    mem[num] = [];
  }
  mem[num].push(n);
}

for (let n = spoken.length; n < 30000000; n++) {
  let last = spoken[n - 1],
    next;

  if (mem[last] && mem[last].length > 1) {
    const turns = mem[last];
    next = turns[turns.length - 1] - turns[turns.length - 2];
  } else {
    next = -1;
  }

  if (next === -1) {
    spoken.push(0);
    if (!mem[0]) {
      mem[0] = [n];
    } else {
      mem[0].push(n);
    }
    continue;
  }

  spoken.push(next);

  if (!mem[next]) {
    mem[next] = [n];
  } else {
    mem[next].push(n);
  }
}

console.log(spoken[spoken.length - 1]) // 31916

Edit:

Even, when reducing the 2nd Version to 3000000 iterations (10x less), it takes much longer, didn't actually wait until it finished.

Edit 2021-01-23: I have added both into running Code Snippet examples. The funny thing is, it doesn't have the runtime problems as described above when running inside the Code Snippets. The Problems occur when running them in my Visual Code debugger locally.

Map vs Object Time complexity (Node.js)

0 Answers