어쩌다 Map과 Object에 대해 Deep Dive하게 됐을까 ❓

Map과 Object에 대해 Deep Dive하게 된 계기

경험상 key, value를 저장해야하는 컬렉션으로 대부분 { } 를 사용했었다. 작성하는 코드의 양이 적기 때문이다. 저장 순서가 보장되어야 하는 경우에만 Map 을 사용했다. Map과 { } 모두 Hash Table을 사용하고 있어, 성능상의 차이는 없다고 생각했다. 하지만 아래의 문제를 푸는 과정에서 내가 가진 정보들이 틀렸다는 사실을 인지하게 됐다.

문제 요약 : [4000][4]의 숫자 배열이 들어오는데
[x1][1] + [x2][2] + [x3][3] + [x4][4] = 0을 만족하는
x1,x2,x3,x4의 경우의 수를 구하는 문제다.

ex) [3453][1] + [2443][2] + [13][3] + [1524][4] = 0을 만족하는 경우의 수 세기
해당 문제 링크

4중 for문의 경우의 수는 4000^4 이기에 시간 초과가 난다고 판단했고, 2중 for문으로 2 열씩 묶어서 더한 값을 key, 해당 key의 등장 수를 value로 저장해서 사용하기로 했다. key의 최대 경우의 수는 4000 * 4000으로 1600만이다.

1, 2열의 모든 경우의 수를 더한 뒤 해당 값을 key, 등장 빈도를 value로 저장하는 로직

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const key = input[i][0] + input[j][1];
      if (!sumDic[key]) sumDic[key] = 1;
      else sumDic[key] += 1;
    }
}

3,4열을 더하고 -를 붙인 key가 { }에 있는지 체크후 있으면 등장 빈도를 결과값에 더하는 로직

let result = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const key = -(input[i][2] + input[j][3]);
      if (sumObj[key]) result += sumObj[key];
  }
}

결과는 아래와 같다.

4000 * 4000 = 16000000 이고 { } 가 해쉬 테이블이니 삽입과 업데이트가 O(1) 이기 때문에 충분히 해결 가능한 풀이법이라 생각했었다.

💡 일반적으로 대략 1억 번의 연산이 1초 걸린다고 판단한다.

💡 Hash Table은 사용하는 hash함수나 해시 충돌시에 해결하는 방법에 따라 성능이 다르지만, 아래와 같은 시간복잡도를 따른다. 대게는 O(1)이다.! 🦀

한참을 고민해도 해당 로직보다 더 효율적인 로직은 없다고 판단들어 { } 대신 Map 로 같은 로직을 구현해 걸리는 시간을 측정했다. Map 으로 구현한 코드가 훨씬 빠른것을 확인했고 해당 문제에 대한 solve를 받을 수 있었다. 약 4배 이상 빠른 것을 확인할 수 있었다.

function random() {
  return parseInt(Math.random() * 2 ** 28 * 2 - 2 ** 28);
}

const n = 4000;
const input = [];
for (let i = 0; i < 4000; i += 1) {
  const row = [];
  for (let abcd = 0; abcd < 4; abcd += 1) {
    row.push(random());
  }
  input.push(row);
}

const solutionMap = () => {
  const sumMap = new Map();

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const key = input[i][0] + input[j][1];

      if (sumMap.has(key)) {
        sumMap.set(key, sumMap.get(key) + 1);
      } else sumMap.set(key, 1);
    }
  }

  let result = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const key = -(input[i][2] + input[j][3]);
      if (sumMap.has(key)) {
        result += sumMap.get(key);
      }
    }
  }
  console.log(result);
};

const solutionObj = () => {
  const sumObj = {};

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const key = input[i][0] + input[j][1];
      if (!sumObj[key]) sumObj[key] = 1;
      else sumObj[key] += 1;
    }
  }

  let result = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const key = -(input[i][2] + input[j][3]);
      if (sumObj[key]) result += sumObj[key];
    }
  }

const main = () => {
  console.time("{ }");
  solutionObj();
  console.timeEnd("{ }");
  console.time("Map");
  solutionMap();
  console.timeEnd("Map");
};

main();
  console.log(result);
};

기존에 갖고 있던 생각

{ } 와 Map 가 같은 자료구조를 가진다면 Map 이 당연히 더 느릴거라고 판단 했었다. 왜냐면 보통의 Hash Table은 입력한 key의 순서를 보장하지 않기 때문이다. Map 이 Hash Table이라면, key 입력 순서를 보장하기 위해 key의 입력을 저장할 로직이 추가적으로 필요하다. 순회 순서를 보장하는 로직이 추가적으로 존재하는 Map 이 더 빠른 것은 논리적이지 않다고 생각했고, 궁금증을 해결하기 위해 Deep Dive하기로 결정했다.