In this article, I will introduce a small story about Java that I usually use at work.
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.
Consider the following implementation using the Stream API introduced in Java 8.
list1
About the elements contained inlist2
If not included in, the resultresultlist
I 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 processing
O (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 }
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;
}
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