cache의 data structure에 따른 성능 차이

[highballplz]

decode-ways 문제를 복습하는 과정에서 질문이 있어 드립니다.

코드 1과 2를 보시면 알고리즘은 dfs로 같고, cache를 map으로 뒀는지(1) array로 뒀는지(2)에서만 차이가 있습니다.

그런데 leetcode를 돌려보면 1은 40 ~ 50ms 근방으로 나오고, 2는 70 ~ 80ms가 나와 두 배까지 차이가 납니다.

map이든 array든 read와 write는 O(1)인데 왜 이런 결과가 나오는지 궁금합니다.

그리고 저는 map이 dynamic하게 hashing해가면서 저장하고 읽어오기 때문에 1이 오히려 더 오래 걸릴 거라고 생각했습니다.

감사합니다 ^^

(1)

const numDecodings = function(s) {
    const cache = new Map();
    cache.set(s.length, 1);

    return dfs(s, 0, cache);
}

const dfs = function(s, i, cache) {
    if (cache.has(i)) return cache.get(i);

    if (s[i] === "0") return 0;
    let count = dfs(s, i + 1, cache);

    if (
    i + 1 < s.length &&
    (s[i] === "1" || (s[i] === "2" && s[i + 1] >= "0" && +s[i + 1] <= "6"))
    )
      count += dfs(s, i + 2, cache);
    cache.set(i, count);
    return count;
}

(2)

const numDecodings = function (s) {
  const cache = new Array(s.length);
  cache[s.length] = 1;

  return dfs(s, 0, cache);
};

const dfs = function (s, i, cache) {
  if (cache[i]) return cache[i];

  if (s[i] === "0") return 0;
  let count = dfs(s, i + 1, cache);

  if (
    i + 1 < s.length &&
    (s[i] === "1" || (s[i] === "2" && s[i + 1] >= "0" && +s[i + 1] <= "6"))
  )
    count += dfs(s, i + 2, cache);
  return (cache[i] = count);
};

[HC-kang]

@highballplz 안녕하세요 하이볼님!
제 생각에는 두 함수의 로직에 차이가 있어보입니다.

위쪽 함수의 경우 if (cache.has(i)) return cache.get(i);를 사용하고
아래쪽 함수의 경우 if (cache[i]) return cache[i];를 사용하는데,

위의 경우 값이 0인 경우에도 해당 값을 재활용하지만, 아래의 경우에는 cache[i] = 0인 경우, false 처리되어 메모를 활용하지 못하고 다시 계산을 하게되는것으로 보입니다.
해당 내용 수정해서 테스트 결과 4~50ms정도로 유사하게 나오네요!

[highballplz]

와우... 그걸 생각 못했네요.

array보다 map이 read write에 있어서 더 효율적이라는 오해를 할 뻔했는데 덕분에 궁금증이 시원하게 해결됐습니다.

사소하다고 생각하실 수 있는 문제였는데 직접 테스트까지 해서 답변 달아주셔서 정말 감사합니다!