본문 바로가기

Javascript Fast Deque

작성

JS는 내장 큐/덱이 없습니다. 대부분은 라이브러리를 사용하겠지만, 구현해야 할 경우도 어디에 있겠죠. 일반적으로 덱을 구현할 때 Array를 사용하면 삽입 및 삭제에 O(N)\mathcal{O}(N), 연결 리스트를 사용하면 삽입 및 삭제에 O(1)\mathcal{O}(1)이 걸린다고 알려져 있습니다. 때문에 연결 리스트 구현이 잘 알려져 있는 것 같습니다. 다만 연결 리스트는 컴퓨터 친화적이지 않아 속도가 실용적이지 않을 때가 있습니다. 이때 Array를 사용하되 삽입 밎 삭제에 분할 상환amortizedO(1)\mathcal{O}(1)이 걸리는 덱의 구현을 소개합니다. 설명은 코드 아래를 참고해 주세요.

Here is the code:

class Deque {
  constructor() {
    this.buf = [,];
    this.front = 0;
    this.back = 0;
  }
  length() {
    const len = this.back - this.front;
    return len < 0 ? len + this.buf.length : len;
  }
  isEmpty() {
    return this.front === this.back;
  }
  double() {
    const length = this.buf.length << 1;
    if (this.back < this.front) {
      const buf = this.buf.slice(this.front);
      for (let i = 0; i < this.back; ++i)
        buf.push(this.buf[i]);
      this.buf = buf;
    }
    this.buf.length = length;
    this.front = 0;
    this.back = (length >> 1) - 1;
  }
  push(v) {
    let back = this.back + 1;
    if (back === this.buf.length)
      back = 0;
    if (back === this.front)
      this.double();
    this.buf[this.back++] = v;
    if (this.back === this.buf.length)
      this.back = 0;
  }
  pop() {
    if (--this.back < 0)
      this.back += this.buf.length;
    return this.buf[this.back];
  }
  shift() {
    const v = this.buf[this.front++];
    if (this.front === this.buf.length)
      this.front = 0;
    return v;
  }
  unshift(v) {
    let front = this.front - 1;
    if (front < 0)
      front += this.buf.length;
    if (front === this.back)
      this.double();
    if (--this.front < 0)
      this.front += this.buf.length;
    this.buf[this.front] = v;
  }
}

설명

큐의 크기가 고정되어 있다면 환형 큐circular queue를 쉽게 구현하여 삽입, 삭제에 O(1)\mathcal{O}(1)이 걸리게 할 수 있습니다. 배열에서 큐의 맨 앞, 맨 뒤를 나타내는 인덱스를 저장하여 이를 앞뒤로 움직이며 자료를 저장하죠.

문제는 길이를 미리 알지 못하는 경우입니다. 이때는 길이가 어느 수준에 도달하면 큐의 크기를 키울 필요가 있는데, 값의 복사가 일어나므로 삽입에 O(N)\mathcal{O}(N)이 걸리기 쉽습니다. 큐의 크기를 항상 22의 거듭제곱으로 유지하면, 큐의 크기가 2K2^K에 도달하기 위해 일어난 값의 복사가 2K12^K - 1회가 됩니다. 큐의 크기를 NN으로 두면, 값의 복사가 O(N)\mathcal{O}(N)번 일어나는 것이죠. 삽입이 O(N)\mathcal{O}(N)번 일어났을 때 값의 복사가 O(N)\mathcal{O}(N)번 일어나므로, 값의 복사는 삽입 한 번당 O(1)\mathcal{O}(1)만큼 일어난다고 볼 수 있습니다. 이러한 시간복잡도 분석 방법을 분할 상환 분석Amortized Analysis이라고 합니다.

배열을 늘릴 때 점차 크게 늘리며 삽입의 시간복잡도를 분할 상환 O(1)\mathcal{O}(1)로 유지하는 이 방법은 사실 대부분의 가변 길이 배열에서 사용되는 방식입니다.

도움이 되셨으면 좋겠습니다. 오류나 누락된 설명, 질문 등은 댓글 혹은 [email protected]로 부탁드립니다. 감사합니다.