[JavaScript] 배열과 커스텀 큐 성능 차이

많은 양의 데이터를 큐로 다뤄야 된다면
빌트인 배열보다는 커스텀 큐를 사용하는 게 성능에 좋습니다!

https://gist.github.com/ChoDragon9/561b5a59d961a31c179c5f836464a5db

더 많은 콘텐츠를 보고 싶다면?

또는

이미 회원이신가요?

2024년 5월 19일 오전 9:17

 • 

저장 56조회 2,540

댓글 2

  • - 내장 배열의 shift 메서드: JavaScript의 내장 배열에서 shift 메서드는 첫 번째 요소를 제거하고 나머지 요소들을 앞으로 한 칸씩 이동시키기 때문에, 배열의 길이에 비례하여 시간이 걸리므로, 큐의 크기가 클수록 성능 저하가 발생합니다. 즉, 매 shift 호출마다 배열의 모든 요소를 이동시켜야 하므로, 반복적으로 shift를 호출하면 총 수행 시간이 급격히 증가합니다. queue.push(i)는 O(1) 시간 복잡도를 가지고, queue.shift()는 O(n) 시간 복잡도를 가집니다. - 커스텀 큐: 커스텀 큐는 배열의 인덱스를 이용하여 head를 증가시키는 방식으로 구현됩니다. 요소를 제거할 때 배열의 요소들을 이동시키지 않고 단순히 head 인덱스를 증가시키기만 하므로, 시간 복잡도가 O(1)이라서 요소를 제거하는 작업이 매우 빠르게 이루어집니다. queue.push(i)는 O(1) 시간 복잡도를 가지고, queue.shift()는 단순히 head 인덱스를 증가시키므로 O(1) 시간 복잡도를 가집니다.

    @peter 설명하신게 맞습니다! 내장 배열의 shift 메서드의 단점을 보완하기 위해 head를 사용한 코드입니다 :)