[Javascript] Set에 대한 얄팍한 정리

 

틀린 내용이 있을 수 있습니다.
잘못된 부분을 발견하시면 말씀 부탁드립니다! 🙇

---

 

 

 

Javascript에서 Set을 이용해 코드를 작성한 적이 종종 있었고 코딩테스트 연습 문제들을 풀면서도 사용한 적이 있었다. 당시에도 사용하면서 왜 빠르지?를 궁금해하긴 했지만 이런저런 핑계 때문에 자세히 찾아보기를 미뤘다. 최근 알고리즘 문제를 풀다 Set을 이용해 속도 효율성 문제를 해결했고, 이 기회에 Javascript에서의 Set에 대해 정확히 이해하자 생각하여 정리해 본다.

 

 

1. Set의 정의와 특징

MDN에서 Set의 정의를 보면 'Set objects are collections of values.'라 나와있듯 Set은 여러 개 값들의 모음이다. 이 여러 개 값들의 모음인 Set에는 원시값(String, Number, Bigint, Symbol, Boolean, Undefined, Null)과 객체, 객체 참조값을 삽입할 수 있다. 또한 Set에 들어있는 값은 중복되지 않으며 중복된 값을 판단할 때에는 SameValueZero 알고리즘을 사용하기 때문에 -0과 +0, NaN과 NaN을 모두 동일한 값으로 본다. 그리고 Set의 요소는 삽입한 순서대로 정렬되기 때문에 삽입한 순서대로 순회 가능하다. (이 부분은 파이썬과 다른 점이니 헷갈리지 말자)

// Javascript
let a = new Set([1,2,3,4,5])
a.add(6)
a.add(0)
a.add(-1)
a.add(100)
a.add(50)

console.log(a.values()) // 결과: {1,2,3,4,5,6,0,-1,100,50}

# Python
a={1,2,3,4,5}
a.add(6)
a.add(0)
a.add(-1)
a.add(100)
a.add(50)

print(a) # 결과: {0, 1, 2, 3, 4, 5, 6, 100, 50, -1}

 

2. Set과 Array 비교

Keyed collection / Indexed collection

Set은 키 기반 컬렉션(Keyed collection)이고 Array는 인덱스 기반 컬렉션(Indexed collection)이다. 풀어서 이야기하면 Set은 키 값을 기반으로 값을 저장하기 때문에 키 값을 이용해 데이터 존재 여부를 확인할 수 있고, Array는 인덱스를 기반으로 값을 저장하는 구조이기 때문에 인덱스 값을 이용해 데이터를 조회할 수 있다.

중복 값 존재 가능 여부

Array는 중복되는 값이 존재할 수 있고 Set에는 중복되는 값이 존재하지 않는다. Array는 인덱스 기반 컬렉션이기 때문에 인덱스가 다르다면 이미 동일한 값이 존재한다 하더라도 저장이 가능한 반면, Set은 키 기반 컬렉션이기 때문에 동일한 키가 존재한다면 이에 대응되는 값이 저장될 수 없기 때문이다.

 

삽입/조회/삭제

Array와 Set 객체에 값을 추가, 조회, 삭제하면서 속도를 비교해 보았다.

let newArr = [];
let newSet = new Set();

function addItemToArr() {
    console.time('addItemToArr');
    for (let i = 0; i < 100000; i++) {
        newArr.push(i);
    }
    console.timeEnd('addItemToArr');
}

function addItemToSet() {
    console.time('addItemToSet');
    for (let i = 0; i < 100000; i++) {
        newSet.add(i);
    }
    console.timeEnd('addItemToSet');
}

addItemToArr(); // Array 객체에 값 추가: 2.0439453125 ms
addItemToSet(); // Set 객체에 값 추가: 6.200927734375 ms

function readItemFromArr() {
    console.time('readItemFromArr');
    for (let i = 0; i < 100000; i++) {
        newArr.includes(i);
        // newArr.indexOf(i);
    }
    console.timeEnd('readItemFromArr');
}

function readItemFromSet() {
    console.time('readItemFromSet');
    for (let i = 0; i < 100000; i++) {
        newSet.has(i);
    }
    console.timeEnd('readItemFromSet');
}

readItemFromArr(); // Array 객체의 값 조회: 2.43017578125 ms
readItemFromSet(); // Set 객체의 값 조회: 1.802001953125 ms

function delItemFromArr() {
    console.time('delItemFromArr');
    for (let i = 0; i < 100000; i++) {
        newArr.splice(i,1);
    }
    console.timeEnd('delItemFromArr');
}

function delItemFromSet() {
    console.time('delItemFromSet');
    for (let i = 0; i < 100000; i++) {
        newSet.delete(i);
    }
    console.timeEnd('delItemFromSet');
}

delItemFromArr(); // Array 객체에서 값 삭제: 1325.258056640625 ms
delItemFromSet(); // Set 객체에서 값 삭제: 5.688232421875 ms

예상대로 조회와 삭제 연산 시 Set이 Array보다 빨랐다. 의외였던 것은 삽입 연산이었다. 단순히 'Set이 Array보다 빠르다' 정도로만 알고 있었기에 Set의 add도 Array의 push보다 빠를 것이라 생각했기 때문이었다. Array의 push가 Set의 add보다 빠른 이유를 추측해 보자면, push는 배열에 중복 값 존재 여부와 상관없이 값을 추가하지만 add는 집합에 중복 값이 있는지 체크를 하고 중복 값이 없으면 값을 삽입하므로 이러한 중복 체크로 인해 속도 차이가 발생하는 게 아닐까 싶다. (근데 다른 포스팅 글을 읽어보니 Set은 해시테이블 방식으로 구성되어 있기 때문에 add에서 중복 체크하는 로직도 시간복잡도가 약 O(1) 일 정도로 최적화된 상태라고 한다...🤔) 만약 중복값을 허용하지 않는다는 조건을 명시할 경우, addItemToArr 함수에 중복체크 로직을 추가해야 하며 이 때는 Set의 add를 사용하는 게 속도적인 측면에서 훨씬 효율적이긴 하다.

 

 

3. 언제 Set을 사용하면 좋을까?

• 중복된 값 없이 요소를 저장해야 할 때. (비슷한 맥락으로 배열에서 중복값을 제거하고 싶을 때 Set을 활용할 수 있다)
• 삽입된 순서대로 요소의 정렬이 보장되어야 할 때.

 

 

 

---

참고 자료

• https://tc39.es/ecma262/multipage/keyed-collections.html#sec-set.prototype.add
• https://medium.com/front-end-weekly/es6-set-vs-array-what-and-when-efc055655e1a
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/values
• https://www.tutorialspoint.com/how-to-make-your-code-faster-using-javascript-sets
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness#same-value-zero_equality
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/is
• https://2ality.com/2015/01/es6-set-operations.html