new Set으로 배열 중복값 제거(with 퍼포먼스 테스트)

💡 지금까지는 배열안의 중복되는 값을 1번과 같이 fileter와 indexOf를 이용하여 제거하였다. 하지만, 이는 시간복잡도가 O(n^2)임을 알 게 된 후, 개선된 방법에 대해 고민하였다. 그러다 최근에 정리한 new Set이 떠올랐고 Set을 이용한 방법을 소개하려고 한다.

 

1. filter && indexOf ⇒ O(n^2)

let arr = [1, 2, 3, 1, 1, 3, 2];
arr = arr.filter((num, idx) => arr.indexOf(num) === idx)

 

---

2. new Set이용 ⇒ O(n)??⭐️

let arr = [1, 2, 3, 1, 1, 3, 2];
arr = [...new Set(arr)];

new Set은 중복된 값을 자동으로 제거 한다는 점을 이용하여, 위와 같은 방식을 생각해봤다.

이곳 저곳 찾아본 결과 new Set의 add메소드의 경우, O(1)이며, new Set은 O(n)이라는 것을 알았다. ⇒ 맞는지 정확하지 않다. 추후에 업데이트 할 예정.

---

⭐️3. 퍼포먼스 차이(filter vs new Set)⭐️

물론, 머리로는 O(n^2)와 O(n)이니 차이가 나겠지 생각은 했지만, 실제로 얼마나 차이가 나는지 궁금해 테스트를 해보았다.

1. 먼저 filter를 이용한 중복값 제거의 모습이다. 환경에 따라 다르겠지만, 4895ms 이 소요된 것을 볼 수 있다.

1. new Set을 이용한 모습 ⇒ 15ms, 배열값을 백만개로 늘렸을때도, 79ms밖에 소요되지 않는다.

물론 다른 분들은 많이 쓰는 방법이겠지만... 이제 입문한 개발자로써,

내가 새롭게 배운 것으로 혼자 스스로 생각해낸 방법이라, 이렇게 성능 개선이 이루어지는 것을 보니, 새삼 뿌듯하다.

 

1. filter && indexOf ⇒ O(n^2)

let arr = [1, 2, 3, 1, 1, 3, 2];
arr = arr.filter((num, idx) => arr.indexOf(num) === idx)

2. new Set이용 ⇒ O(n)??⭐️

let arr = [1, 2, 3, 1, 1, 3, 2];
arr = [...new Set(arr)];

new Set은 중복된 값을 자동으로 제거 한다는 점을 이용하여, 위와 같은 방식을 생각해봤다.

이곳 저곳 찾아본 결과 new Set의 add메소드의 경우, O(1)이며, new Set은 O(n)이라는 것을 알았다. ⇒ 맞는지 정확하지 않다. 추후에 업데이트 할 예정.