Consider implementing a method that returns the difference between two Lists

Introduction

In this article, I will introduce a small story about Java that I usually use at work.

Problem setting

Suppose you want to implement a method that "removes elements in one list 1 from elements in another list 2". There are several situations in which such a feature can be useful. For example, when implementing a function to recommend a user in a Web service, put the ID of the user who is a candidate for recommendation in Listing 1 and the ID of the user who should be excluded from the recommendation candidate for some reason in Listing 2, and the final user. It is used to present the recommendation results.

――Hereafter, we will proceed with the list elements as Integer type, but it is not limited to Integer type in particular, and there is no problem even if it is complicated like `List <String>`. --Each list shall not contain duplicate elements. (From a practical point of view, think of such duplication as being eliminated before the method is called.)

Collection#removeAll The first method implementation I came up with was:

1st


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

It's concise and easy to read, but it's less desirable because you've changed the arguments. It is possible to copy the list with the `` `clone``` method, but this time we will consider another method.

Another direction: Java 8 Stream API

Consider the following implementation using the Stream API introduced in Java 8. list1About the elements contained inlist2If not included in, the resultresultlistI will add it to.

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;
}

There are likely to be some improvements in this implementation as well.

--`new ArrayList <> (); You can pass the result of` `list1.stream ()` to resultListas it is without creating a new instance with` ``. --Calling the `` `.contains ()` `` method on a list requires processingO (n) ``` (Java 8 streams how to filter contents a List not found in another arrayList? )

Regarding the second point, in the above implementation, `list2.contains ()` is called for each element of `list1```, so in total ```O (n) ^ 2) It will be necessary to process . ([java /util/AbstractCollection.java](http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractCollection.java#AbstractCollection.contains) In% 28java.lang.Object% 29), you can see that `` .contains ()` `` follows each element one by one.)

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    }

Third honesty: .contains () for Set

Consider the following implementation, which improves the above points. Using `.contains ()` for Set, the process of determining whether the element of `list1``` is included in ``` list2``` is ```O (1) I was able to suppress it to `.

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;
}

By the way

In Apache Commons Collections, [ListUtils.java](https://commons.apache.org/proper/commons- In collections / apidocs / src-html / org / apache / commons / collections4 / ListUtils.html), the `` `subtract``` method is defined as follows.

python


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    }

Recommended Posts

Consider implementing a method that returns the difference between two Lists
[Android] Easily calculate the difference between two dates
What is the difference between a class and a struct? ?? ??
Calculate the difference between numbers in a Ruby array
Now in the third year, the misunderstanding that I noticed is the difference between the equals method and ==
What is the difference between an action and an instance method?
Let's override the difference between == (identity) and equals method (equivalence)
[Ruby] Method that returns truth
[Ruby] Difference between symbol variables and character string variables. About the difference between [: a] and ['a'].
Output the difference between each field of two objects in Java
What is the difference between a web server and an application server?
Easy to understand the difference between Ruby instance method and class method.
[Java] You might be happy if the return value of a method that returns null is Optional <>
Difference between instance method and class method
Difference between render method and redirect_to
Find the difference between List types
Difference between == operator and equals method
Difference between == operator and eqals method
Understand the difference between each_with_index and each.with_index
Find the angle between two vectors
Was that so, the user_signed_in? method
Declare a method that has a Java return value with the return value data type
Sample program that returns the hash value of a file in Java
[Rails] I studied the difference between new method, save method, build method and create method.