JavaでVector,HashMap,LinkedListのループ時間を計測してみる

夜中にふと思い立って Java のループ実行時間の計測をしたのですが、折角なので共有します。

前置き

適当に思いついた方法を試していっただけなので厳密性には欠けると思います。参考程度にしてください。
Java初心者の実験メモです。

実験その１

とりあえず思いついたものを書いて実行してみる。
それぞれ100万個の要素を持たせてそれをすべて参照するループをワンセットで計測しました。
実行するたびにランキングが逆転したりするので、100回実行した結果の平均を参考にするようにしてます。
ちなみにLinkedListくんのfor文は実行時間がとんでもなく長かったので論外としてコメントアウトしてあります。使い方が間違ってるんでしょうか。

forLoopTest.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Vector;


public class forLoopTest {

	public static void main(String[] args) {

		int loopMax = 100;		// 試行回数
		int dataCnt = 1000000;	// 変数の要素数

		// 実行時間を記憶する変数(サイズ適当)
		ArrayList<Long> times = new ArrayList<Long>(100);
		for(int i=0; i < 100; i++) {
			times.add(i,(long) 0);
		}

		// Vectorに100万件データ登録
		Vector vect = new Vector();
		for(int i=0; i < dataCnt; i++) {
			vect.add(i);
		}
		// HashMapに100万件データ登録
		HashMap hm = new HashMap();
		for(int i=0; i < dataCnt; i++) {
			hm.put(i,i);
		}
		// LinkedListに100万件データ登録
		LinkedList ls = new LinkedList<>();
		for(int i=0; i < dataCnt; i++) {
			ls.add(i);
		}

		long start;
		long end;
		for(int loop=0; loop<loopMax; loop++) {

			/* --Vector-- */
			// for文でループ
			start = System.currentTimeMillis();
	        for (int i=0; i < vect.size(); i++) {
	            Object tmp = vect.get(i);
	        }
			end = System.currentTimeMillis();
			times.set(0, times.get(0) + (end - start));

			// for文でループ(終了条件を変数に)
			start = System.currentTimeMillis();
	        for (int i=0,len=vect.size(); i<len; i++) {
	            Object tmp = vect.get(i);
	        }
			end = System.currentTimeMillis();
			times.set(1, times.get(1) + (end - start));

			// 拡張for文でループ
			start = System.currentTimeMillis();
	        for (Object elm : vect) {
	            Object tmp = elm;
	        }
			end = System.currentTimeMillis();
			times.set(2, times.get(2) + (end - start));


			/* --HashMap-- */
			// for文でループ
			start = System.currentTimeMillis();
	        for (int i=0; i < hm.size(); i++) {
	            Object tmp = hm.get(i);
	        }
			end = System.currentTimeMillis();
			times.set(3, times.get(3) + (end - start));

			// for文でループ(終了条件を変数に)
			start = System.currentTimeMillis();
	        for (int i=0,len=hm.size(); i<len; i++) {
	            Object tmp = hm.get(i);
	        }
			end = System.currentTimeMillis();
			times.set(4, times.get(4) + (end - start));

			// 拡張for文でループ
			start = System.currentTimeMillis();
	        for (Object elm : hm.keySet()) {
	            Object tmp = elm;
	        }
			end = System.currentTimeMillis();
			times.set(5, times.get(5) + (end - start));

			// 拡張for文(keySetArray)でループ
			Object[] keyArr = hm.keySet().toArray();
			start = System.currentTimeMillis();
	        for (Object elm : keyArr) {
	            Object tmp = hm.get(elm);
	        }
			end = System.currentTimeMillis();
			times.set(6, times.get(6) + (end - start));


			/* --LinkedList-- */
			// for文でループ
//			start = System.currentTimeMillis();
//	        for (int i=0; i < ls.size(); i++) {
//	            Object tmp = ls.get(i);
//	        }
//			end = System.currentTimeMillis();
//			times.set(7, times.get(7) + (end - start));
//
//			// for文でループ(終了条件を変数に)
//			start = System.currentTimeMillis();
//	        for (int i=0,len=ls.size(); i<len; i++) {
//	            Object tmp = ls.get(i);
//	        }
//			end = System.currentTimeMillis();
//			times.set(8, times.get(8) + (end - start));
//
			// 拡張for文でループ
			start = System.currentTimeMillis();
	        for (Object elm : ls) {
	            Object tmp = elm;
	        }
			end = System.currentTimeMillis();
			times.set(9, times.get(9) + (end - start));
		}

		System.out.println("Vector");
		System.out.println("for文: " + ((float)times.get(0) / (float)loopMax) + " ms");
		System.out.println("for文 終了条件が変数: " + ((float)times.get(1) / (float)loopMax) + " ms");
		System.out.println("拡張for文: " + ((float)times.get(2) / (float)loopMax) + " ms");
		System.out.println("");
		System.out.println("HashMap");
		System.out.println("for文: " + ((float)times.get(3) / (float)loopMax) + " ms");
		System.out.println("for文 終了条件が変数: " + ((float)times.get(4) / (float)loopMax) + " ms");
		System.out.println("拡張for文: " + ((float)times.get(5) / (float)loopMax) + " ms");
		System.out.println("拡張for文 keySet: " + ((float)times.get(6) / (float)loopMax) + " ms");
		System.out.println("");
		System.out.println("LinkedList");
//		System.out.println("for文: " + ((float)times.get(7) / (float)loopMax) + " ms");
//		System.out.println("for文 終了条件が変数: " + ((float)times.get(8) / (float)loopMax) + " ms");
		System.out.println("拡張for文: " + ((float)times.get(9) / (float)loopMax) + " ms");
	}

}

実行結果

実験その１の実行結果は以下の通りとなった。

Vector
for文: 19.39 ms
for文 終了条件が変数: 9.07 ms
拡張for文: 19.21 ms

HashMap
for文: 10.52 ms
for文 終了条件が変数: 9.4 ms
拡張for文: 11.12 ms
拡張for文 keySet: 7.41 ms

LinkedList
拡張for文: 8.27 ms

終了条件を変数にするとかなり速度が上がった。特にVectorで半分以下になっている。何度か実行したが、毎回おおよそ50%の速度向上がみられた。
最速はHashMapの拡張for文。keySetを予め配列に落としておき、それをループするのが速かった。でもこれってHashMapのループじゃなくて配列の拡張forループが速いんじゃなかろうか・・・。兎に角HashMapの全要素を参照するときは直接じゃなく、keySet配列の軽量なループの中でkeyで参照しようということですね。

• 終了条件は変数にして、sizeやlengthを毎周みないようにする。
• HashMapはkeySet配列 + 拡張for文で回す。

実験その２

配列のループが速そうなので、Vectorを一回配列にしてからループにかけてみる。
結局これが速そうな予感がします笑
なんパターンか追加します。

			// 配列に変換してループ
			Integer[] arr = (Integer[])vect.toArray(new Integer[vect.size()]);
			start = System.currentTimeMillis();
	        for (int i=0; i < arr.length; i++) {
	            Object tmp = arr[i];
	        }
			end = System.currentTimeMillis();
			times.set(10, times.get(10) + (end - start));

			// 配列に変換してループ(終了条件を変数に)
			Integer[] arr2 = (Integer[])vect.toArray(new Integer[vect.size()]);
			start = System.currentTimeMillis();
	        for (int i=0,len=arr2.length; i<len; i++) {
	            Object tmp = arr2[i];
	        }
			end = System.currentTimeMillis();
			times.set(11, times.get(11) + (end - start));

			// 配列に変換してループ(変換時間加味)
			start = System.currentTimeMillis();
			Integer[] arr3 = (Integer[])vect.toArray(new Integer[vect.size()]);
	        for (int i=0; i < arr3.length; i++) {
	            Object tmp = arr3[i];
	        }
			end = System.currentTimeMillis();
			times.set(12, times.get(12) + (end - start));

			// 配列に変換してループ(終了条件を変数にして変換時間加味)
			start = System.currentTimeMillis();
			Integer[] arr4 = (Integer[])vect.toArray(new Integer[vect.size()]);
	        for (int i=0,len=arr4.length; i<len; i++) {
	            Object tmp = arr4[i];
	        }
			end = System.currentTimeMillis();
			times.set(13, times.get(13) + (end - start));

実行結果

実験その２の実行結果は以下の通りとなった。

Vector
for文: 20.19 ms
for文 終了条件が変数: 9.68 ms
拡張for文: 20.16 ms
配列に変換してループ: 0.1 ms
配列に変換してループ(終了条件を変数に): 0.11 ms
配列に変換してループ(変換時間加味): 4.12 ms
配列に変換してループ(終了条件を変数にして変換時間加味): 3.84 ms

HashMap
for文: 11.46 ms
for文 終了条件が変数: 10.27 ms
拡張for文: 13.16 ms
拡張for文 keySet: 7.82 ms

LinkedList
拡張for文: 10.17 ms

はやっ！
めちゃめちゃ速くなりました！

• 結局普通の配列が速い

まとめ

Javaの高速化のHawToを実証するだけみたいな感じになりましたが、改めて以下のことがわかりました。

• for文の終了条件にsizeやlengthをとる際は、変数に入れて使用するとよい。
• HashMapをループさせるときは、keySetの配列で拡張for文を回すとよい。
• 配列にできるものなら配列に落としてからループさせるとよい。

未だVectorを使っているコードのチューニングをする機会ってなんだかんだありそうですもんね。
その他いろいろ試せることはありますが、ある程度は参考になるデータが取れたかなと思うので寝ます。
おやすみなさい。