JavaのCollectionUtils.containsAllをstreamと遅延処理で見直す

CollectionUtils.containsAllは一つでも要素が存在しない場合はfalseを返します

@Test
public void test_all_contains(){
    List<String> lista = List.of("abc","def","hij");
    List<String> listb = List.of("abc","def","ghi");
    boolean result = CollectionUtils.containsAll(lista,listb);
    assertFalse(result);
    List<String> listc = List.of("abc","def","ghi");
    result = CollectionUtils.containsAll(listb,listc);
    assertTrue(result);
}

CollectionUtils.containsAllの実装は以下のようになっている

public static boolean containsAll(final Collection<?> coll1, final Collection<?> coll2) {
    if (coll2.isEmpty()) {
        return true;
    }
    final Iterator<?> it = coll1.iterator();
    final Set<Object> elementsAlreadySeen = new HashSet<>();
    for (final Object nextElement : coll2) {
        if (elementsAlreadySeen.contains(nextElement)) {
            continue;
        }

        boolean foundCurrentElement = false;
        while (it.hasNext()) {
            final Object p = it.next();
            elementsAlreadySeen.add(p);
            if (nextElement == null ? p == null : nextElement.equals(p)) {
                foundCurrentElement = true;
                break;
            }
        }

        if (!foundCurrentElement) {
            return false;
        }
    }
    return true;
}

一度見つかった要素に関してはelementsAlreadySeenに入るので要素の数までは見ていません。そのため以下のようなコードはtrueです

@Test
public void test_all_contains_(){
    List<String> lista = new ArrayList<>();
    lista.add(null);
    lista.add(null);
    lista.add(null);
    lista.add("abc");
    lista.add("abc");
    lista.add("abc");

    List<String> listb = new ArrayList<>();
    listb.add(null);
    listb.add("abc");

    boolean result = CollectionUtils.containsAll(lista,listb);
    assertTrue(result);
}

しかしこのコードはifもforもwhileも使っているので頭が痛くなりますね

以下のように修正してみましょう。

public static boolean containsAll(final Collection<?> cola ,final Collection<?> colb){
    long result = cola.stream().filter( a -> !colb.contains(a)).count();
    if(result >= 1){
        return false;
    }
    return true;
}

これでテストしても機能として通っています

しかし処理時間に関しては疑問が残りますよね？以下のテストで簡易的に実行時間差を見てみます

@Test
public void test_perf(){

    class Item{
        public final int id;
        public final String name;
        public Item(int id, String name){
            this.id = id;
            this.name = name;
        }
    }

    List<Item> lista = new ArrayList<>();
    List<Item> listb = new ArrayList<>();
    // 超絶大量のインスタンス
    for(int i = 0; i < 30000; i++){
        Item item = new Item(i,"商品" + String.valueOf(i));
        lista.add(item);
        listb.add(item);
        // これは別のインスタンスなので調査不可能
        // lista.add(new Item(i,"商品" + String.valueOf(i)));
        // listb.add(new Item(i,"商品" + String.valueOf(i)));
    }

    long startTime = System.currentTimeMillis();
    boolean result = CollectionUtils.containsAll(lista,listb);
    assertTrue(result);
    long endTime = System.currentTimeMillis();
    System.out.println("処理時間：" + (endTime - startTime) + " ms");


    startTime = System.currentTimeMillis();
    boolean myresult = MyMapUtils.containsAll(lista,listb);
    endTime = System.currentTimeMillis();
    System.out.println("処理時間：" + (endTime - startTime) + " ms");
    assertTrue(myresult);
}

計測した時間は大差がついてます

処理時間：25 ms 処理時間：908 ms

これはfilterの中で他のコレクションにアクセスしているため遅くなっています（遅くなっていると思います） Setに詰め替えることでこれは解決できます

public static boolean containsAll(final Collection<?> cola ,final Collection<?> colb){
    Set<?> set = new HashSet<>(colb);
    long result = cola.stream().filter( a -> !set.contains(a)).count();
    if(result >= 1){
        return false;
    }
    return true;
}

処理時間：26 ms 処理時間：5 ms

圧倒的なパフォーマンスの差を出しました。

しかしまだです。まだ、パフォーマンスで負ける可能性がありますこれは全て走査するので無駄な処理が走ってしまいます元々は1件でもあればその時点でfalseが返却されるのと、elementsAlreadySeenのようなtemp変数が用意されているため速いです

以下のコードでテストしてみます

@Test
public void test_perf(){
    class Item{
        public final int id;
        public final String name;
        public Item(int id, String name){
            this.id = id;
            this.name = name;
        }
    }

    List<Item> lista = new ArrayList<>();
    List<Item> listb = new ArrayList<>();
    // 件数を増やす30000→300000
    for(int i = 0; i < 300000; i++){
        Item item = new Item(i,"商品" + String.valueOf(i));
        lista.add(item);
        // listbにだけ違うデータを仕込む
        if(i == 3){
            listb.add(new Item(999999,"ダミー"));
            continue;
        }
        listb.add(item);
    }

    long startTime = System.currentTimeMillis();
    boolean result = CollectionUtils.containsAll(lista,listb);
    assertFalse(result);
    long endTime = System.currentTimeMillis();
    System.out.println("処理時間：" + (endTime - startTime) + " ms");

    startTime = System.currentTimeMillis();
    boolean myresult = MyMapUtils.containsAll(lista,listb);
    endTime = System.currentTimeMillis();
    System.out.println("処理時間：" + (endTime - startTime) + " ms");
    assertFalse(myresult);
}

処理時間：104 ms 処理時間：76 ms

まだ速度で負けてないのですが、その差が縮まっています。

というわけで更に改善します。これはstreamの遅延処理を使っています

public static boolean containsAll(final Collection<?> cola ,final Collection<?> colb){
    Set<?> set = new HashSet<>(colb);
    return cola.stream().filter( a -> !set.contains(a)).findFirst().isEmpty();
}

処理時間：98 ms 処理時間：34 ms

圧倒的な速さです。

これはなぜでしょうか？

実はfilterメソッドは一度に全ての要素を検索するわけではありません。まずfilterで要素が見つかった場合は、次のチェーンへと処理を渡します。今回の場合はfindFirstメソッドです。これは最初の1件を返すメソッドです。

このfindFirstは終端処理であり、ここで終了条件を満たすとチェーンはそこで終了します。そのため、もしもfilterで要素が見つかると、findFistで終了条件が満たされ処理終了します。 filterは最後まで処理を行うことをしません。これが遅延処理です。

最初はcount関数を使っていたため、終端処理で処理が終了しません(終了するのに必要な要素が取得できていない)ので、終端処理が次の要素を求めます。そこで処理がfilterに戻ってきてノロノロと処理を続けていたのです。 streamを使うと読みやすさだけでなくパフォーマンスも改善されるということが分かったかと思います。

※計測は必ずしも正確ではありません。あくまで目安程度です。

おまけ

List.ofでリストを作る時にnullを渡すとぬるぽになるので注意

List<String> listc = List.of("aa,", null);

java.lang.NullPointerException

デトフィア

プログラミング

JavaのCollectionUtils.containsAllをstreamと遅延処理で見直す

おまけ