최근 아주 운이 좋게도 너무 읽어보고 싶던 책인 멀티패러다임 프로그래밍의 서평단에 당첨되어 신나는 마음으로 책을 읽고 있다.

절반까지 읽은 현재 대부분의 내용은 이터레이터를 이용해 지연 평가와 관련된 내용들이 다수를 이루고 있다. (좀 더 자세한 내용은 나중에 다 읽고 적도록 한다!)

다양한 메소드에 대한 설명글을 보다가 이터러블한 값들을 잇는 concat 메소드 예시가 나왔고 보자마자 어! 이걸로 큐 쉽게 구현이 되겠는데? 라는 생각이 들어 당장 실험을 해봤고 완전완전 구현이 되어서 신나는 마음으로 포스팅한다.

자바스크립트의 큐

자바스크립트 Array 의 프로토타입 메소드인 unshift , shift 는 배열 첫 번째 인수에 값을 추가하거나 제거하는 메소드이다.

자바스크립트에선 큐를 내장하여 지원하지 않기 때문에 데이터 크기가 N 인 배열 첫 번째에 값을 추가하거나 제거하는 행위는 O(N) 의 시간 복잡도를 갖는다.

데이터를 추가하거나 제거하면 메모리상에 존재하는 모든 값들을 한 칸씩 이동 시켜야 하기 때문이다.

이에 자바스크립트로 알고리즘들을 풀다가 큐가 필요한 경우 매번 연결 리스트 형태로 큐를 구현하곤 했다.

이터러블과 이터레이터

이터러블은 이터레이터를 반환하는 객체이며 이터레이터 객체는 next() 메소드를 통해 본인이 가진 값을 yield 한다.

우리가 for of 문으로 순회하거나 스프레드 연산을 가능하게 하는 것도 객체들이 이터러블이기 때문이다.

제네레이터는 이터러블을 반환하는 함수인데 좀 더 자세한 내용들은 MDN 을 참고하도록 하자

제네레이터를 통해 unshift 구현

function* concat(...args) {
  for (const arg of args) {
    if (arg[Symbol.iterator] && typeof arg[Symbol.iterator] === "function") {
      yield* arg; // 반환할 인수가 iterable이라면 flatten 하여 yield
    } else {
      yield arg;
    }
  }
}

이게 끝이다. 정말 말도 안되게 간단하다.

단순히 인수들을 차례대로 yield 해버리면 된다.

이 때 반환할 객체가 iterable 이라면 내부 값들을 하나씩 yield 한다.
[1,2,3,[4,5,6]] 이라면 1,2,3,4,5,6 으로 yield된다.

구현이라고 하기도 부끄럽다.

한 번 잘 작동하는지 배열의 unshift 와 비교해서 살펴보자

const arrayUnshiftTest = () => {
  let array = Array.from({ length: 1_000_000 }, (_, i) => i);
 
  console.time("arrayUnshiftInsert");
  for (let i = 0; i < 1_000; i++) {
    array.unshift(1_000_000 + i);
  }
  console.timeEnd("arrayUnshiftInsert");
 
  return array;
};
 
const generatorUnshiftTest = () => {
  let iterable = concat(Array.from({ length: 1_000_000 }, (_, i) => i));
 
  console.time("generatorUnshift");
  for (let i = 0; i < 1_000; i++) {
    iterable = concat(1_000_000 + i, iterable); // 첫 번째 값 추가
  }
  console.timeEnd("generatorUnshift");
 
  return iterable;
};
 
const array = arrayUnshiftTest();
const iterable = generatorUnshiftTest();
 
console.log(iterable.next().value);
console.log(iterable.next().value);
console.log(iterable.next().value);

arrayUnshiftInsert: 166.674ms
generatorUnshift: 0.141ms
1000999
1000998
1000997

첫 번째에 값을 추가하는 행위가 제네레이터쪽이 훨씬 빠른건 너무나 자명하다.

배열처럼 내부 값들을 모두 이동시킬 필요가 없고 단순히 새로운 이터러블을 생성해주기만 하면 되기 때문이다.

실제 큐처럼 dequeue 하는 행위는 그냥 반환된 이터러블에서 .next() 메소드를 호출해주면 되고 enqueue 하는 행위는 현재 이터러블을 이용해 앞에 데이터를 추가한 새로운 이터러블을 생성해주면 된다.

push 를 하고 싶다면 concat(iterable , newDate) 를 이용해주면 된다.

제한 사항

물론 연결리스트로 구현된 큐에 비해 pop 이 O(1) 만에 되지는 않는다는 점이 제한사항 일 것이다.

길이를 구한다거나 값을 제거하지 않고 출력만 하는 행위는 어떻게 구현하면 될 거 같긴하지만 말이다.

그래도 가끔씩 정말 FIFO 만을 위해 필요한 자료구조를 생성 할 때 해당 방법을 사용하면 너무 편하게 구현 할 수 있을 거 같다.

그리고 좀 더 고수같아 보인다랄까 호호호