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

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

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

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


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

```java: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```に追加していきます。

```java: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?
](https://stackoverflow.com/questions/42730691/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](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractCollection.java#AbstractCollection.contains%28java.lang.Object%29)の中で、```.contains()```が要素を1つ1つ追っているのが確認できます。)

```java: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)```に抑えることができました。

```java: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](https://mvnrepository.com/artifact/org.apache.commons/commons-collections4/4.1)では、[ListUtils.java](https://commons.apache.org/proper/commons-collections/apidocs/src-html/org/apache/commons/collections4/ListUtils.html)の中で```subtract```メソッドを以下のように定義しています。

```java:
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    }
```