Javaで学ぶアルゴリズム -スタック（java.util.Stack と java.util.ArrayDeque のパフォーマンス比較）

Javaでの効率的なスタック実装：ArrayDeque vs Stack

Javaの標準ライブラリには java.util.Stack と java.util.ArrayDeque という二つのスタック実装があるけど、

スタックとして使われるときはStackよりも高速

と言われているので検証。

実行環境

• Java 8
• ヒープサイズ：-Xms512m -Xmx1024m で設定

テスト（検証用）コード

• スタックの基本的な操作である push / pop / peek をそれぞれ 1000000 回やる
• System.nanoTime() を使用して、1000000 回実行したときのナノ秒単位の時間を取得する

StackPerformanceTest.java

import java.util.ArrayDeque;
import java.util.Stack;

public class StackPerformanceTest {

	private static final int OPERATIONS_COUNT = 1000000;

	public static void main(String[] args) {

		long[] stackTimes = measureStackPerformance();
		long[] dequeTimes = measureArrayDequePerformance();

		System.out.println("Operation\tStack (ns)\tArrayDeque (ns)");
		System.out.println("Push\t\t" + stackTimes[0] + "\t\t" + dequeTimes[0]);
		System.out.println("Peek\t\t" + stackTimes[1] + "\t\t" + dequeTimes[1]);
		System.out.println("Pop\t\t" + stackTimes[2] + "\t\t" + dequeTimes[2]);
	}

	private static long[] measureStackPerformance() {
		Stack<Integer> stack = new Stack<>();
		long pushTime = 0;
		long peekTime = 0;
		long popTime = 0;

		long pushStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.push(i);
		}
		pushTime += System.nanoTime() - pushStart;

		long peekStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.peek();
		}
		peekTime += System.nanoTime() - peekStart;

		long popStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.pop();
		}
		popTime += System.nanoTime() - popStart;

		return new long[] { pushTime, peekTime, popTime };
	}

	private static long[] measureArrayDequePerformance() {
		ArrayDeque<Integer> deque = new ArrayDeque<>();
		long pushTime = 0;
		long peekTime = 0;
		long popTime = 0;

		long pushStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.push(i);
		}
		pushTime += System.nanoTime() - pushStart;

		long peekStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.peek();
		}
		peekTime += System.nanoTime() - peekStart;

		long popStart = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.pop();
		}
		popTime += System.nanoTime() - popStart;

		return new long[] { pushTime, peekTime, popTime };
	}
}

実行結果

平均値比較（※ 単位はナノ秒）

観点 \ ライブラリ	java.util.Stack	java.util.ArrayDeque
push	20,356,860	6,374,430
peek	17,176,950	254,450
pop	19,884,760	795,100

各回比較（※ 単位はナノ秒）

回	Stack	Stack	Stack	ArrayDeque	ArrayDeque	ArrayDeque
-	push	peek	pop	push	peek	pop
1	28770200	34148300	44782999	14775600	2544100	3526000
2	27759301	15423599	15435001	13483700	0	536701
3	25714001	15431900	15267799	6342900	0	519700
4	16711800	15421600	15442400	3009800	0	475001
5	16810599	15161099	15479701	2940400	100	477399
6	22395800	15311601	15372400	3061600	100	544300
7	16666500	16591599	32503301	3013500	0	474600
8	16678900	15316400	15426399	11209401	100	488500
9	16178200	14491301	14553700	2948001	0	454999
10	15883300	14472101	14583899	2959400	100	453800

優位に java.util.ArrayDeque の方がパフォーマンスよいことが分かるけど、ArrayDequeのpeeks処理があまりにも最適化されてそう（キャッシュの影響かなぁ？）なので、プログラムを書き換えて再実行してみる。

テスト（検証用）コードその２

計測の仕様を以下のように変更したうえで、全体のパフォーマンスを測定してみる。

• すべての要素を push する
• その後 peek と pop を繰り返す
• 1000000 この要素分の push / peek / pop の合計時間を測定

StackPerformanceTest.java

import java.util.ArrayDeque;
import java.util.Stack;

public class StackPerformanceTest {

	private static final int OPERATIONS_COUNT = 1000000;

	public static void main(String[] args) {

		StringBuilder sb = new StringBuilder();
		sb.append("回数, java.util.Stack, java.util.ArrayDeque");
		sb.append(System.lineSeparator());

		for (int i = 1; i < 11; i++) {

			long stackTimes = measureStackPerformance();
			long dequeTimes = measureArrayDequePerformance();

			sb.append(i + ", " + stackTimes + ", " + dequeTimes);
			sb.append(System.lineSeparator());
		}
		System.out.println(sb.toString());
	}

	private static long measureStackPerformance() {
		Stack<Integer> stack = new Stack<>();
		long stackTime = 0;

		long start = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.push(i);
		}

		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			stack.peek();
			stack.pop();
		}
		stackTime = System.nanoTime() - start;

		return stackTime;
	}

	private static long measureArrayDequePerformance() {
		ArrayDeque<Integer> deque = new ArrayDeque<>();
		long dequeTime = 0;

		long start = System.nanoTime();
		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.push(i);
		}

		for (int i = 0; i < OPERATIONS_COUNT; i++) {
			deque.peek();
			deque.pop();
		}

		dequeTime = System.nanoTime() - start;

		return dequeTime;
	}
}

実行結果

とはいえ、優位に java.util.ArrayDeque の方がパフォーマンスよいね。

平均値比較（※ 単位はナノ秒）

回数 \ ライブラリ	java.util.Stack	java.util.ArrayDeque
平均	38,941,760	6,880,650

各回比較（※ 単位はナノ秒）

回数	java.util.Stack	java.util.ArrayDeque
1	88,468,199	17,380,101
2	41,395,700	13,799,700
3	39,710,899	7,140,700
4	30,828,800	3,426,101
5	31,008,800	3,410,800
6	36,107,300	3,417,100
7	30,359,300	3,375,900
8	30,327,900	10,002,101
9	30,658,101	3,418,000
10	30,552,600	3,435,999