リスト型のcontains​がどの程度遅いのか今度こそはっきりさせる

公開・非公開問わずソースコードを見ているとjava.util.List系のコレクションに対してcontainsメソッドを呼び出しているのを見かけます。

個人的にはcontains使うならjava.util.Set系のコレクションだろというのが染みついているので違和感があるのですが、仮にList系でも件数が少なければそれほど速度を気にすることもないというのは理解できます。

というわけで要素数の違いによってList系とSet系のcontainsでどの程度速度差が出るのかJMHを使って検証しました。

以下のベンチマークはあくまで特定のPC上で行ったもので、誰がやっても同じ結果が出るとは限りません。
ListとSetでの速度差が明確に出てくる要素数も環境によって変わる可能性があるので、あくまで参考程度に捉えてください。

ベンチマーク環境

• OS
  • Windows10Pro
• CPU
  • Core i7-10700 (8core 16thread)
• Memory
  • 32GB
• Java
  • OpenJDK11
• Apache Maven
  • 3.6.3

コード

実際のコード一式はGitHubにアップしてあります。

以下、抜粋して要点を書きます。

データの準備

まず10000件のデータを準備します。
ListやSetの要素はIntegerとして0から9999までの値を順番に入れます。

要素数による速度差を調べるためにそれぞれ
3件、100件、200件、300件、500件、1000件を元のListから切り出して作成し、それをもとにSetも作成します。

    private List<Integer> list, list3, list100, list200, list300, list400, list500, list1000;
    private Set<Integer> hash, hash3, hash100, hash200, hash300, hash400, hash500, hash1000;
    private Random random;

    @Setup(Level.Trial)
    public void setup() {
        list = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            list.add(i);
        }
        hash = new HashSet<>(list);
        list3 = list.subList(0, 3);
        list100 = list.subList(0, 100);
        list200 = list.subList(0, 200);
        list300 = list.subList(0, 300);
        list400 = list.subList(0, 400);
        list500 = list.subList(0, 500);
        list1000 = list.subList(0, 1000);
        hash3 = new HashSet<>(list3);
        hash100 = new HashSet<>(list100);
        hash200 = new HashSet<>(list200);
        hash300 = new HashSet<>(list300);
        hash400 = new HashSet<>(list400);
        hash500 = new HashSet<>(list500);
        hash1000 = new HashSet<>(list1000);
        random = new SecureRandom();
    }

ベンチマーク用コード

ベンチマーク用コードはいたって簡単でそれぞれのListやSetに対してランダムで値を検索します。

今回はヒットする場合のみの調査ということでランダムの範囲はサイズと等しくしてあります。

    @Benchmark
    public void list10000byRandom() {
        list.contains(random.nextInt(10000));
    }

    @Benchmark
    public void hash10000byRandom() {
        hash.contains(random.nextInt(10000));
    }

    @Benchmark
    public void list3byRandom() {
        list3.contains(random.nextInt(3));
    }

    @Benchmark
    public void hash3byRandom() {
        hash3.contains(random.nextInt(3));
    }

    // 以下それぞれのListやSetに対してメソッドを記述

ベンチマーク実行

実行はJMHの作法に従って以下のコマンドを入れるだけです。

実行中はCPUパワーをガンガン使いますし、完了まで時間がかかるので他の作業がない時にやったほうがいいです。

$ mvn clean install
$ java -jar target/benchmarks.jar

結果

ベンチマーク中は途中でいろいろ情報が表示されますが、比較は最後に出る情報を見ればわかります。

Benchmark                                 Mode  Cnt        Score       Error  Units
LinearSearchBenchmark.hash10000byRandom  thrpt   25  3193215.598 ± 20949.809  ops/s
LinearSearchBenchmark.hash1000byRandom   thrpt   25  3365810.112 ± 14012.113  ops/s
LinearSearchBenchmark.hash500byRandom    thrpt   25  3362976.178 ± 27262.871  ops/s
LinearSearchBenchmark.hash400byRandom    thrpt   25  3365370.778 ± 19847.586  ops/s
LinearSearchBenchmark.hash300byRandom    thrpt   25  3334358.009 ± 29671.475  ops/s
LinearSearchBenchmark.hash200byRandom    thrpt   25  3350009.934 ± 34307.637  ops/s
LinearSearchBenchmark.hash100byRandom    thrpt   25  3409502.179 ± 20199.082  ops/s
LinearSearchBenchmark.hash3byRandom      thrpt   25  3419157.438 ± 30087.527  ops/s
LinearSearchBenchmark.list10000byRandom  thrpt   25   303243.224 ± 17902.836  ops/s
LinearSearchBenchmark.list1000byRandom   thrpt   25  1646142.208 ± 11763.362  ops/s
LinearSearchBenchmark.list500byRandom    thrpt   25  2243831.031 ± 13802.357  ops/s
LinearSearchBenchmark.list400byRandom    thrpt   25  2388511.159 ± 26325.934  ops/s
LinearSearchBenchmark.list300byRandom    thrpt   25  2546713.315 ±  9975.117  ops/s
LinearSearchBenchmark.list200byRandom    thrpt   25  2764345.888 ± 26634.541  ops/s
LinearSearchBenchmark.list100byRandom    thrpt   25  3046888.524 ± 27270.219  ops/s
LinearSearchBenchmark.list3byRandom      thrpt   25  3365787.785 ± 19028.487  ops/s

※Scoreが高い方が高速

メソッド名の辞書順に実行されるようで変な並びですが、この結果からわかることは

• Setは10000件までなら件数にかかわらず速い。（※10000件までしかテストしてないから）
• Listは3件ならSetとほぼ遜色ない速度。
• Listは100件だと若干Setより遅い程度（差にして1割程度？）
• Listは件数が増えるごとにどんどん遅くなる。

まとめ

ここまでの結果から個人的に得られた感触としては

• 元のデータがList型であれば数十件以内のものについてはわざわざSetに入れ替えてcontainsしなくてもよいかも。
• 100件を超えるようであればそもそものデータの持ち方を考え直してSet系のコレクションに対してcontainsするように変更すべき。

という感じです。
長年containsはSetだろと思いつつ強力な説得力のある根拠がなかったのですっきりしました。

おまけ

ここまでListのcontainsがなんで遅いのか書いてませんが、簡単に説明するとcontainsをするときにListの先頭から一致する値がないか調べていくアルゴリズム（線形探索）のため、後ろの方の値を検索するときに遅くなります。
試しにベンチマークプログラムを書き換えて

    @Benchmark
    public void list10000by9999() {
        list.contains(9999);
    }

    @Benchmark
    public void hash10000by0() {
        hash.contains(0);
    }

というメソッドでテストしてみるとわかりやすいです。
先頭に入っている0の検索は速いですが、要素の最後に入っている9999の検索は遅いはずです。