読者です 読者をやめる 読者になる 読者になる

$shibayu36->blog;

株式会社はてなでエンジニアをしています。プログラミングや読書のことなどについて書いています。

高速な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のメモリの確保とかもこんな感じだった記憶がある。

まとめ

今回はCourseraで出てきた高速なRandomized Queueというのを試しに実装してみた。こういう風な簡単な構造でもなかなか考えることが多いし、また他の場所で使われているような配列の拡張のような仕組みが学べて面白かった。

関連