社内でも同じこと書いたのですが、こっちでも。
大きなリスト(例えば10万件を超えるようなもの)から一致するものを探す場合、ArrayList#containsを使うと、パフォーマンス的に問題になる場合があります。ArrayList#containsは、先頭からシーケンシャルに見ていくためです。
で、大きなリストを検索する場合には、検索に向いたデータ形式、例えばHashSetに格納することによって、パフォーマンスが大きく改善する場合があります。HashSetはハッシュテーブルを使って値を格納するので、シーケンシャルに見ていくより高速です。
ということで、試したコードです。 10万件の2つのリストを使って、「リスト1からリスト2に含まれるもののみに絞り込む」といったことをやっています。
package com.example; import static org.assertj.core.api.Assertions.assertThat; import java.util.HashSet; import java.util.List; import java.util.Set; import java.util.stream.Collectors; import java.util.stream.IntStream; import org.junit.Test; public class LargeListFilterTest { private static final int SIZE = 100000; private static final List<String> SOURCE; private static final List<String> CANDIDATE; static { SOURCE = IntStream.rangeClosed(1, SIZE) .mapToObj(String::valueOf) .collect(Collectors.toList()); CANDIDATE = IntStream.rangeClosed(1, SIZE) .map(x -> x * 2) // 偶数のみに .mapToObj(String::valueOf) .collect(Collectors.toList()); } @Test public void filterWithSetのテスト() { List<String> filterd = filterWithSet(SOURCE, CANDIDATE); assertThat(filterd) .hasSize(SIZE / 2); } @Test public void filterWithListのテスト() { List<String> filterd = filterWithList(SOURCE, CANDIDATE); assertThat(filterd) .hasSize(SIZE / 2); } private <T> List<T> filterWithSet(List<T> source, List<T> candidate) { Set<T> candidateSet = new HashSet<>(candidate); return source.stream() .filter(candidateSet::contains) .collect(Collectors.toList()); } private <T> List<T> filterWithList(List<T> source, List<T> candidate) { return source.stream() .filter(candidate::contains) .collect(Collectors.toList()); } }
パフォーマンスの差はあきらかで、下記のような結果になりました。(あくまで自分のPC上でのパフォーマンスですが、差が大きいのは明確です)
- ArrayListの場合: 26.046秒
- HashSetの場合: 0.084秒
なお、小さいリストだったら、いちいちHashSetに変える必要はないです。逆にHashSetにすることによって遅くなる場合もあります。 (小さければシーケンシャルに見たほうが早い場合も多いです。そもそも小さいと気にするレベルの差にもならないですが…)
このようなボトルネックは、プロファイリングかければすぐに見つかるので、パフォーマンスを厳しく求められたり、思った通りのパフォーマンスが出ていないときは、まずはプロファイリングにかけてみると良いです。 JavaだとFlight Recorderが簡単に使えて便利なので、とても助けられています。(それでこういった問題に気がついたことも多いです)