大きなリストを検索するときにArrayListではなくHashSetを使う (Java)

社内でも同じこと書いたのですが、こっちでも。

大きなリスト(例えば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秒

f:id:onozaty:20181103211322p:plain

なお、小さいリストだったら、いちいちHashSetに変える必要はないです。逆にHashSetにすることによって遅くなる場合もあります。 (小さければシーケンシャルに見たほうが早い場合も多いです。そもそも小さいと気にするレベルの差にもならないですが…)

このようなボトルネックは、プロファイリングかければすぐに見つかるので、パフォーマンスを厳しく求められたり、思った通りのパフォーマンスが出ていないときは、まずはプロファイリングにかけてみると良いです。 JavaだとFlight Recorderが簡単に使えて便利なので、とても助けられています。(それでこういった問題に気がついたことも多いです)