코딩테스트 스터디를 만들고 나서 JS로 자료구조와 알고리즘을 공부하는 요즘,
Queue에 대해 문득 드는 의문점을 해결하지 않은 채 둔 게 있습니다.
배열에 shift라는 메서드가 있던데, 그거 쓰면 같은 거 아닌가?
왜 굳이 queue를 구현해서 써야한다고 얘기하는거지?
라는 내용인데요.
이참에 의문점을 파고들어 해소하고 지나치자는 생각에 오늘도 한 편의 글을 남기게 되었습니다.
시작하기 앞서
스택오버플로우에서 2018년도에 올라온 질문이 있습니다
Array.shift와 링크드리스트 방식의 퍼포먼스 차이에 대한 질문인데요.
한번 보고 오면 좋을 것 같습니다
요약하자면,
5만개 기준으로, 5만개보다 적은 경우엔 30-40%정도 느리다고 하며
5만개의 요소를 넘어가는 순간부터는 100%만큼 느리다고 답변이 달려있습니다.
큐를 구현하는 방식
기본적으로 2가지 방식이 있다고 알려져 있습니다.
1. Class Queue - 링크드 리스트
소스코드 기본 형태는 다음과 같습니다(완벽한 형태가 아닙니다).
class Queue {
constructor() {
this.storage = {};
this.headIndex = 0;
this.tailIndex = 0;
}
enqueue(item) {
this.storage[this.tailIndex] = item;
this.tailIndex++;
}
dequeue() {
const item = this.storage[this.headIndex];
delete this.storage[this.headIndex];
this.headIndex++;
return item;
}
getLength() {
return this.tailIndex - this.headIndex;
}
getItem() {
return this.storage[this.headIndex];
}
}
JavaScript
복사
2. Array.shift() + Array.push()
사실, 배열 방식에서 원소를 넣어주는 push메서드에서 시간 차이가 발생하진 않습니다.
그러나, shift()의 경우엔 다음과 같은 내부로직이 존재합니다
•
array[0]에 접근해서 값을 반환하고 배열에서 제거
•
array[0]의 값은 없어도 공간은 차지중 → 나머지 배열의 원소들을 한칸씩 앞으로 당겨주기
마지막 과정에서 원소들을 한칸씩 앞으로 당겨주기에, 추가 소요시간이 발생하게 되고 queue를 실제 구현해서 사용하는 것보다 느리다고 이야기들을 하는 것입니다.
결론
물론, 데이터 개수가 많지 않은 경우(50K이하 말고, 한참 적은 데이터 개수일때)엔 문제가 되지 않을 것 같습니다
데이터 개수가 많지 않는 테스트를 진행해야하는 코딩테스트의 경우라던지, 아직 유저 데이터가 많지 않은 경우라던지를 생각하면, 귀찮게 코드 몇 줄 더 적고 사용할 필요있나 싶을지도 모르겠습니다.
그래도 우리가 왜 “클린코드”라던지, “디자인 패턴”이나 “객체지향의 사실과 오해”같은, 좋은 코드를 작성하는 것에 대해서 학습을 할까요?
저는 그런 행동의 모든 것이 결국 우리가 앞으로 작성할 코드들이 모두 확장하기 좋고, 리뷰하기 쉽고, 수정하기 쉬운 형태로 만들어두기 위해서라고 생각합니다. 결국 언젠가는 모두 레거시 코드가 되겠죠?
제 코드가 언제 레거시 코드가 될 지는 알 수 없을 겁니다.
그러니 지금 당장 좀 귀찮다고 생각이 될 지라도, 진정 이 분야에서 오래 머물고 싶은 생각이 있다면 현재의 내가 좀 더 수정하기 쉬운 형태로 만들어놔야한다고 생각합니다.
그러니까, 데이터 개수가 적다고 shift() 메서드를 사용하기보다는, class로 큐를 구현해서 사용하는 습관을 갖는 것이 좋을 것 같습니다.
그치만, 시간싸움의 경우(코딩테스트)같은 케이스에 한해서는 문제가 안된다면 그냥 잠시 사용해도 문제가 없지 않을까요?
근데, JS도 진화하지 않았을까요?
JS는 여전히, 그리고 요즘들어 참 많이 생태계 발전에 맞춰 변화하고 개선되고 있다고 생각이 되는데요
그렇다면, JS도 이런 문제를 모를리가 없고
개선해놓은 무언가가 있지 않을까 싶었습니다.
그래서 한 번 찾아봤습니다.
역시 저는 참신한 생각을 잘 못 해내는 편인가 같아요,,, 더 좋은 방식을 생각해내는 사람들이 참 많은 것 같아요. 계속 아는 내용도 갱신하시는 분들도 많고,,
1. 최신 JS는 배열이 해시구조라서 괜찮다!
윗 사진의 내용을 제가 한 번 찾아보긴 했는데, 결국 다음과 같은 얘기와 같은 맥락인 것 같습니다.
여러분들 혹시 “자바스크립트에서 배열은 객체다”라는 얘기를 들어보셨나요?
제가 모던 자바스크립트 DeepDive를 읽어보면서 본 적 있는 내용인데요. 자바스크립트는 흔히들 “리스트같은 객체”라고 많이 얘기들을 합니다. 다음과 같은 특징들이 있기 때문이예요
1.
JS의 배열은 인덱스를 키로 사용하고, length 속성을 갖는 특수 객체
a.
그치만, 유사배열객체라는 것도 존재하는데
유사배열객체는 Array내장 메서드를 사용할 수 없습니다(≠ 배열)
2.
배열의 prototype은 객체
근데, 솔직히 그렇다고 해도, shift()메서드 자체의 내부 동작이 원소들이 앞으로 당겨지는 과정이 포함되어있다고 하니..
개인적인 생각으로는 많은 데이터를 다룰 생각이 없는 게 아닌 이상은 큐를 직접 구현하는 형태로 사용하는게 맞을 것 같습니다.
2. Map객체를 이용해서 class를 구현하면 더 좋을 것 같다!
Map객체를 사용해서 만든다…
새로 생긴 문법을 활용해 바로 이런 방식을 떠오르지 못한 제 자신…반성해야할 것 같습니다..
이 방식은 위쪽에서 제가 적어놓은 기본적인 틀의 class와 유사한 방식으로 작동하면서도
key값만 필요하다던지, value값만 필요한 경우일때도 Object.keys나 Object.values, for…of같은 것으로도 더 다양하게 활용할 수 있는 장점이 있다고 판단됩니다(Map 객체니까요).
