QueueやStackとして使うなら‥LinkedList vs ArrayDeque
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クラスのソースを覗いてみよう‥