高速なRandomized Queueのアルゴリズムを実装する

CourseraのAlgorithms, Part Iというコースで、高速なRandomized Queueを実装するという話題があったので、試しに作ってみた。

高速なRandomized Queueとは

Randomized Queueとは、Queueからdequeueするときに、中に入っている要素の中からランダムに一要素取り出すようなQueueである。

また「高速な」とは、enqueue、dequeue、isEmpty、sizeなどの操作の実行時間が、"constant amortized time"であること、つまり何回も操作を繰り返していくと、平均的には定数時間でそれぞれの操作が終わるということである。

この二つを満たすものを高速なRandomized Queueと呼ぶ。

実装

高速なRandomized Queueを実装すると次のようになった。

import java.util.NoSuchElementException;

public class RandomizedQueue<Item> {
  private Item[] queue;
  private int N;

  public RandomizedQueue() {
    N = 0;
    queue = (Item[]) new Object[1];
  }

  public boolean isEmpty() {
    return N == 0;
  }

  public int size() {
    return N;
  }

  public void enqueue(Item item) {
    // queueのサイズが足りなくなったら配列を2倍にする
    if (N == queue.length) this.resize(2 * queue.length);
    queue[N++] = item;
  }

  public Item dequeue() {
    if (this.isEmpty()) {
      throw new NoSuchElementException();
    }

    // ランダムな位置から要素を取り出し、queueの最後の要素をその位置に移動する
    int i = (int) (Math.random() * N);
    Item item = queue[i];
    queue[i] = queue[N - 1];
    queue[N - 1] = null;
    N--;

    // queueのデータ量が、queueの最大長の1/4以下になったらqueueを1/2に縮める
    if (0 < N && N <= queue.length / 4) this.resize(queue.length / 2);

    return item;
  }

  private void resize(int capacity) {
    Item[] newQueue = (Item[]) new Object[capacity];
    for (int i = 0; i < N; i++) {
      newQueue[i] = queue[i];
    }
    queue = newQueue;
  }
}

今回の実装で注目するところは以下の二点。

dequeue操作が定数時間になるために配列を利用する
利用者側が配列の長さを意識しなくて良いように、うまく内部でresizeする

dequeue操作が定数時間になるために配列を利用する

よくあるQueueの実装のときはLinkedListのような構造を使うことが多い。しかしLinkedListで実装した場合、dequeueがランダムに要素を取り出すという仕様だと、取得したい位置までLinkedListを辿る操作が必要となってくる。すると辿る操作はQueueのサイズNに比例する時間がかかるため、O(n)の実行時間となってしまう。

今回はdequeue操作もO(1)で行わなければならないので、LinkedList構造は使えない。そのため、内部では配列を利用することになる。

利用者側が配列の長さを意識しなくて良いように、うまく内部でresizeする

Queueの内部実装で配列を使う場合、今持っている配列の長さ以上にデータをenqueueされた時に配列を拡張する必要がある。これもうまくやらないとO(1)の計算量とならない。

今回は次のように配列の拡張・縮小を行った。

配列の長さ以上にenqueueされたら、内部の配列の長さを2倍に拡張する
dequeueが続き、今の配列の長さの1/4しかデータが入ってない状態になったら、内部の配列の長さを1/2に縮小する

enqueueで2倍に拡張する瞬間はO(n)の計算量が発生するが、それでもenqueueを続けていくと平均的にはO(1)の計算量になるらしい。詳しくはCourseraを見てほしい。

また、1/4しかデータが入っていない時に配列の長さを1/2にする理由は、スラッシングの防止のためである。「配列に1/2しかデータが入っていない状態になったら長さを1/2にする」という実装にしてしまうと、ちょうど1/2のデータ量の時にenqueue, dequeue, enqueue, dequeue, ...と交互に繰り返すと毎回resizeが発生してしまい遅くなってしまう。しかし、今回のような縮小方法にすれば、そのようなときでもresizeがたくさん発生することはない。

ちなみにこのように内部的に長さを2倍にしていくような実装は色んな所で見られるらしい。あまり良く知らないけど、Golangのスライスの実装もこういう風になっているみたいだし、確かLinuxのメモリの確保とかもこんな感じだった記憶がある。