はじめに
Javaのリストである、SetとListの処理速度を計測し、性能を比較してみました。
SetはHashSet、ListはArrayListで計測しています。
計測
add
1000万未満の正の整数を追加して比較してみました。
Set<Integer> set = new HashSet<>();
long start1 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
set.add(i);
}
long end1 = System.currentTimeMillis();
System.out.println("Set: " + (end1 - start1) + "ms");
List<Integer> list = new ArrayList<>();
long start2 = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
list.add(i);
}
long end2 = System.currentTimeMillis();
System.out.println("List: " + (end2 - start2) + "ms");Set: 3878ms
List: 1388msListのほうが速いです。
contains
10万未満の正の整数に対し、存在するランダムな値が含まれているかを10万回確認しています。
Set<Integer> set = new HashSet<>();
for (int i = 0; i < 100000; i++) {
set.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
set.contains((int) (Math.random() * set.size()));
}
long end1 = System.currentTimeMillis();
System.out.println("Set: " + (end1 - start1) + "ms");
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list.add(i);
}
long start2 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
list.contains((int) (Math.random() * list.size()));
}
long end2 = System.currentTimeMillis();
System.out.println("List: " + (end2 - start2) + "ms");Set: 16ms
List: 3658msSetのほうが速いです。
remove
10万未満の正の整数に対し、ランダムで一致する要素を10万回削除しています。
Set<Integer> set = new HashSet<>();
for (int i = 0; i < 100000; i++) {
set.add(i);
}
long start1 = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
set.remove(Integer.valueOf((int) (Math.random() * 100000)));
}
long end1 = System.currentTimeMillis();
System.out.println("Set: " + (end1 - start1) + "ms");
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
list.add(i);
}
long start2= System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
list.remove(Integer.valueOf((int) (Math.random() * 100000)));
}
long end2 = System.currentTimeMillis();
System.out.println("List: " + (end2 - start2) + "ms");Set: 15ms
List: 3891msSetのほうが速いです。
おわりに
SetとListの処理速度を比較しました。
addはListのほうが速いですが、containsとremoveはSetのほうが速いです。
大量件数でcontainsやremoveを頻繁に行う場合には、Listだとかなりの性能問題となり得るので、極力Setを使用してください。
Setは重複した要素を持てず、順序を保持しないという特性があるのでその点は注意してください。
