[JS] Array vs. Set

백준 1920번 문제를 해결하면서 Set과 Array는 속도 차이가 나는지 차이가 난다면 얼마나 나는지, 특정 상황에서 어떤 구조가 더 빠른지 찾아보았다. 

 

Set 객체는 Map 객체와 함께 자바스크립트 ES6 버전에서 생긴 기능이다. 속도에 관한 내용을 찾던 도중 Set이 나왔을 당시 성능에 대한 내용과 현재는 어떤 지 알아볼 수 있는 글을 찾았다.

 

1.

Set,Map 등이 처음 나왔을 당시 스택오버플로우에서 첫 요소의 추가, 변경, 삭제에 대해 테스트 케이스를 만들어 수행한 결과를 찾았는데, 일반적으로 Array가 빠르지만 입력받는 숫자가 아주 크다면 delete 메서드를 사용해 요소를 삭제하는 경우에 한하여 Set 이 압도적으로 빠르다는 내용이었다.

 

 하지만 속도를 비교하기에 테스트 케이스가 적절한가에 대한 댓글있었고, 질문이 올라왔던 2016년과 댓글을 다는 2018년에 동일한 테스트를 진행했는데 Set의 속도가 비약적으로 올랐다는 글도 있었다. 2년간 map과 set의 연산 속도가 빨라졌을 거라는 내용이다.

 

2.

 테스트 할 수 있는 예제를 가져와 직접 속도를 출력 해보았다. 아주 간단한 입력을 받는 테스트이기에 일방적으로 한쪽이 빠르다고 결론짓기는 아쉬운 테스트이지만 요소의 확인, 추가, 삭제에서 속도 차이를 알아볼 수 있다.

// 사용할 입력

var n = 100000;
// 더 높은 케이스를 사용할 수도 있지만, [Maximum call stack size exceeded] 에러가 발생하므로, 이정도만 확인 해보도록 한다.
var arr = Array.apply( null, Array( n ) ).map( ( x, i ) => i );
console.info( arr.length ); 
var checkArr = ( arr, item ) => arr.indexOf( item ) !== -1;
var checkSet = ( set, item ) => set.has( item );

// Vars
var set, result;

(1) 요소의 확인

console.time( 'timeTest' );
result = checkArr( arr, 123123 );
console.timeEnd( 'timeTest' );	// timeTest: 0.14ms

set = new Set( arr );

console.time( 'timeTest' );
checkSet( set, 123123 );
console.timeEnd( 'timeTest' );	// timeTest: 0.061ms

console.time( 'timeTest' );
arr.includes(123123)
console.timeEnd( 'timeTest' );	// timeTest: 0.1ms

set = new Set( arr );

console.time( 'timeTest' );
set.has(123123)
console.timeEnd( 'timeTest' );	// timeTest: 0.007ms

 

(2) 요소의 추가

console.time( 'timeTest' );
arr.push( n + 1 );
console.timeEnd( 'timeTest' );	// timeTest: 0.435ms

set = new Set( arr );

console.time( 'timeTest' );
set.add( n + 1 );
console.timeEnd( 'timeTest' );	// timeTest: 0.006ms

console.info( arr.length ); //100001
console.info( set.size );   //100001

 

(3) 요소의 삭제

var deleteFromArr = ( arr, item ) => {
    var i = arr.indexOf( item );
    i !== -1 && arr.splice( i, 1 );
};

console.time( 'timeTest' );
deleteFromArr( arr, 123123 );
console.timeEnd( 'timeTest' );	// timeTest: 0.142ms

set = new Set( arr );

console.time( 'timeTest' );
set.delete( 123123 );
console.timeEnd( 'timeTest' );	// timeTest: 0.005ms

 

3.

처음 나왔을 당시엔 어땠을지 모르지만, 현재는  일반적으로 Set이 Array 보다 빠르게 출력한다. 

 

 비슷한 실험을 하며 Set의 장점을 소개하는 글을 찾았는데, 코드를 조금 더 빠르고 확장성 있게 만들려면 basic-type(Array)이 항상 좋은 방법은 아닐 것이라고 말한다. 뿐만 아니라 각 테스트에서 어떻게 Set이 빠를 수 있었나 설명도 해줘서 많은 공부가 되는 글이었다.

 

2. 와 유사한 테스트를 해보고 내린 결론

 

 

 

https://stackoverflow.com/questions/39007637/javascript-set-vs-array-performance#comment93399644_39010462

Javascript Set vs. Array performance

https://bretcameron.medium.com/how-to-make-your-code-faster-using-javascript-sets-b432457a4a77

How to make your code faster using JavaScript Sets