リストとセットの検索時間の計測 2015/12

テスト概要

• リストとセットの検索時間を計測する。
• 容量10,000のArrayListとHashSetを用意し、それぞれに0から10,000までの整数を入れる。
• 20,000個の乱数(0～20,000)を用意して、ArrayListはindexOfメソッドで、HashSetはcontainsメソッドで中身に含まれているかを検索する。
• 2回ずつ繰り返して時間を計測する。

---

テスト環境

マシン : 東芝 dynabook R73/W6M
CPU : i7-4710MQ 2.50GHz
MEM : 8GB
OS : Windows 8.1 64bit
Java : 1.8.0.31
Eclipse : 4.4.1

---

実行プログラムコード

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;

public class ListOrSet {

	final int CAPACITY = 10000;
	
	// リストの検索速度と、セットの検索速度を比較するプログラム。
	public static void main(String[] args) {
		
		// アイドリング
		for (int i = 0; i < 100; i++) {
			System.out.println("Do Initialize..." + i);
		}
		
		ListOrSet obj = new ListOrSet();
		
		long timeList = 0L;
		long timeSet = 0L;
		
		Integer[] first = obj.getRandomArray();
		Integer[] second = obj.getRandomArray();
		
		ArrayList testList = obj.initList();
		HashSet testSet = obj.initSet();
		
		timeList += obj.findInList(testList, first);
		timeSet += obj.findInSet(testSet, second);
		
		// 中休み
		for (int i = 0; i < 100; i++) {
			System.out.println("Now Breaking..." + i);
		}

		timeList += obj.findInList(testList, first);
		timeSet += obj.findInSet(testSet, second);
		
		// 結果を表示
		System.out.println("timeList : " + timeList);
		System.out.println("timeSet : " + timeSet);
	}
	
	ListOrSet() {}
	
	// 乱数配列の生成。
	Integer[] getRandomArray() {
		
		int testRange = CAPACITY * 2;
		Random random = new Random();
		Integer[] randoms = new Integer[testRange];
		for (int i = 0; i < testRange; i++) {
			randoms[i] = random.nextInt(testRange);
		}
		
		return randoms;
	}
	
	// テスト用リストの初期可。
	ArrayList initList() {
		
		ArrayList data = new ArrayList(CAPACITY);
		for (int i = 0; i < CAPACITY; i++) {
			data.add(i);
		}
		
		return data;
	}
	
	// テスト用セットの初期化。
	HashSet initSet() {
		
		HashSet data = new HashSet(CAPACITY);
		for (int i = 0; i < CAPACITY; i++) {
			data.add(i);
		}
		
		return data;
	}
	
	// リストに要素が含まれているか検索する。
	// indexOfメソッドを呼ぶ。
	long findInList(ArrayList data, Integer[] randoms) {
		
		int found = -1;
		
		long then = System.currentTimeMillis();
		for (int i = 0; i < randoms.length; i++) {
			found = data.indexOf(randoms[i]);
		}
		long now = System.currentTimeMillis();
		
		return now - then;
	}
	
	// セットに要素が含まれているか検索する。
	// containsメソッドを呼ぶ。
	long findInSet(HashSet data, Integer[] randoms) {

		boolean found;
		
		long then = System.currentTimeMillis();
		for (int i = 0; i < randoms.length; i++) {
			found = data.contains(randoms[i]);
		}
		long now = System.currentTimeMillis();
		
		return now - then;
	}
}

---

テスト結果(ミリ秒)

	ArrayList indexOf	HashSet contains
1回目	250	0
2回目	234	16
3回目	235	0
4回目	235	15
5回目	234	0
6回目	234	0
7回目	234	0
8回目	250	0
9回目	234	0
10回目	234	0

---

結論

• 検索速度では、セットは比較にならないほどリストよりも早い。