2つのListの差分を返すメソッドの実装を検討する

はじめに

この記事では、筆者が普段仕事で使っているJavaにまつわる小ネタを紹介します。

問題設定

「あるリスト1の要素から、別のリスト2に含まれている要素を取り除く」機能をメソッドとして実装するとします。このような機能が役に立つシチュエーションは、いくつか考えることができます。例えば、Webサービスでユーザを推薦する機能を実装する時、リスト1に推薦候補となるユーザのID、リスト2に何らかの理由で推薦候補から外すべきユーザのIDを入れておいて、最終的なユーザ推薦結果の提示に利用する、といったものです。

• 以下、リストの要素をInteger型として話を進めますが、特にInteger型に限らず、List<String>のように複雑にしても問題はありません。
• それぞれのリストには、重複する要素が含まれていないものとします。（実務的な観点で言えば、メソッドが呼ばれる前にそのような重複が排除されていると考えて下さい。）

Collection#removeAll

最初に考えついたメソッド実装は、以下のようなものでした。

1st

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2) {
    list1.removeAll(list2);
    return list1;
}

簡潔で見やすいのですが、引数を変更してしまっている点であまり望ましくありません。cloneメソッドでリストをコピーすることも可能ですが、今回は別の方法を考えてみます。

別の方向性: Java 8 Stream API

Java 8 で導入されたStream APIを使って、次のような実装を考えてみます。
list1に含まれる要素について、list2に含まれなければ、結果となるresultListに追加していきます。

2nd

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2){
    final List<List<Integer>> resultList = new ArrayList<>();
    list1.stream()
        .filter(p -> {
            return (! list2.contains(p));
        })
        .forEach(p -> {
            resultList.add(p);
        });
    return resultList;
}

この実装にも、少し改善できそうな点がありそうです。

• new ArrayList<>();で新しいインスタンスを生成しないで、list1.stream()の結果をresultListにそのまま渡せる
• リストに対して.contains()メソッドを呼ぶとO(n)の処理が必要になる (Java 8 streams how to filter contents a List not found in another arrayList?
  )

2点目に関して、上記の実装ではlist1の要素1つ1つに対してlist2.contains()を呼んでいるので、トータルでO(n^2)の処理が必要になってしまいます。(java/util/AbstractCollection.javaの中で、.contains()が要素を1つ1つ追っているのが確認できます。)

AbstractCollection.java

98     public boolean More ...contains(Object o) {
99         Iterator<E> e = iterator();
100        if (o==null) {
101            while (e.hasNext())
102                if (e.next()==null)
103                    return true;
104        } else {
105            while (e.hasNext())
106                if (o.equals(e.next()))
107                    return true;
108        }
109        return false;
110    }

3度目の正直: Setに対する.contains()

上記の点を改善した、以下のような実装を考えてみます。
Setに対する.contains()を使って、list1の要素がlist2に含まれるか判定する部分の処理をO(1)に抑えることができました。

3rd

public static List<Integer> subtract(List<Integer> list1, List<Integer> list2) {
    final HashSet<Integer> list2Set = new HashSet<>(list2);
    final List<Integer> resultList = list1.stream()
            .filter(p -> {
                return (! list2Set.contains(p));
            })
            .collect(Collectors.toList());
    return resultList;
}

ちなみに

Apache Commons Collectionsでは、ListUtils.javaの中でsubtractメソッドを以下のように定義しています。

110    /**
111     * Subtracts all elements in the second list from the first list,
112     * placing the results in a new list.
113     * <p>
114     * This differs from {@link List#removeAll(Collection)} in that
115     * cardinality is respected; if <Code>list1</Code> contains two
116     * occurrences of <Code>null</Code> and <Code>list2</Code> only
117     * contains one occurrence, then the returned list will still contain
118     * one occurrence.
119     *
120     * @param <E> the element type
121     * @param list1  the list to subtract from
122     * @param list2  the list to subtract
123     * @return a new list containing the results
124     * @throws NullPointerException if either list is null
125     */
126    public static <E> List<E> subtract(final List<E> list1, final List<? extends E> list2) {
127        final ArrayList<E> result = new ArrayList<E>();
128        final HashBag<E> bag = new HashBag<E>(list2);
129        for (final E e : list1) {
130            if (!bag.remove(e, 1)) {
131                result.add(e);
132            }
133        }
134        return result;
135    }