HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

QueueやStackとして使うなら‥LinkedList vs ArrayDeque

頭がJava 1.4で止まっているプログラマの呟き(謎)‥

LinkedListをQueueとして使ったあるプログラム(何)を書いていて、QueueやStackとして使うならLinkedListよりArrayDequeがお勧めとアドバイスをもらったので、軽く検証してみた。

事前準備

ソースコードは以下のような感じ。

  • LinkedListAsQueue.java
import java.util.LinkedList;
import java.util.Queue;

public class LinkedListAsQueueTest {
    public static void main(String[] args) {
        Queue<String> q = new LinkedList<>();

        long S = System.currentTimeMillis();
        while (true) {
            q.offer("a");
            long E = System.currentTimeMillis();
            System.err.println("q=" + q.size() + ", " + (E - S) + "ms");
        }
    }
}
  • ArrayDequeAsQueue.java
import java.util.ArrayDeque;
import java.util.Queue;

public class ArrayDequeAsQueueTest {
    public static void main(String[] args) {
        Queue<String> q = new ArrayDeque<>();

        long S = System.currentTimeMillis();
        while (true) {
            q.offer("a");
            long E = System.currentTimeMillis();
            System.err.println("q=" + q.size() + ", " + (E - S) + "ms");
        }
    }
}
  • LinkedListAsStack.java
import java.util.LinkedList;
import java.util.Deque;

public class LinkedListAsStackTest {
    public static void main(String[] args) {
        Deque<String> q = new LinkedList<>();

        long S = System.currentTimeMillis();
        while (true) {
            q.push("a");
            long E = System.currentTimeMillis();
            System.err.println("q=" + q.size() + ", " + (E - S) + "ms");
        }
    }
}
  • ArrayDequeAsStack.java
import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeAsStackTest {
    public static void main(String[] args) {
        Deque<String> q = new ArrayDeque<>();

        long S = System.currentTimeMillis();
        while (true) {
            q.push("a");
            long E = System.currentTimeMillis();
            System.err.println("q=" + q.size() + ", " + (E - S) + "ms");
        }
    }
}

XxxAsStack.javaの方はDequeなので末尾からpush/popする使い方もありだが、わざと先頭に要素を追加する実装にしてある。

実行

長時間待つのが面倒なので、最大ヒープサイズを小さくして実行する。

$ java -Xmx8m <ClassName>

これでOutOfMemoryErrorが出るまで待って最終行を記録、ということを5回ずつ繰り返す。

結果

  • LinkedListAsQueue
q=328077, 6279ms
q=328112, 6165ms
q=328077, 6187ms
q=328077, 6463ms
q=328122, 6526ms
  • ArrayDequeAsQueue
q=524287, 6834ms
q=524287, 6766ms
q=524287, 6697ms
q=524287, 6732ms
q=524287, 6460ms
  • LinkedListAsStack
q=328111, 6309ms
q=328076, 6290ms
q=328085, 6378ms
q=328076, 6134ms
q=328076, 6326ms
  • ArrayDequeAsStack
q=524287, 6769ms
q=524287, 6576ms
q=524287, 6545ms
q=524287, 7081ms
q=524287, 6917ms

それぞれの平均をまとめると以下のような感じ。

要素の数 時間(ms) 要素の数/時間(ms)
LinkedListAsQueue 328093.0 6324.0 51.881
ArrayDequeAsQueue 524287.0 6697.8 78.277
LinkedListAsStack 328084.8 6287.4 52.181
ArrayDequeAsStack 524287.0 6777.6 77.356

確かに、メモリ使用量の観点からも速度の観点からもLinkedListよりArrayDequeの方がQueueやStackに向いていそう。速度的にはLinkedListの方が早いのかなと勝手に思っていたが違うのか‥ちょっとArrayDequeクラスのソースを覗いてみよう‥