[JAVA] Erwägen Sie die Implementierung einer Methode, die die Differenz zwischen zwei Listen zurückgibt

Einführung

In diesem Artikel werde ich eine kleine Geschichte über Java vorstellen, die ich normalerweise bei der Arbeit verwende.

Problemstellung

Angenommen, Sie möchten eine Methode implementieren, die "Elemente in einer Liste 1 aus Elementen in einer anderen Liste 2 entfernt". Es gibt verschiedene Situationen, in denen eine solche Funktion nützlich sein kann. Wenn Sie beispielsweise eine Funktion zum Empfehlen von Benutzern in einem Webdienst implementieren, geben Sie die ID des Benutzers, der ein Empfehlungskandidat ist, in Listing 1 und die ID des Benutzers, der aus irgendeinem Grund von den Empfehlungskandidaten in Liste 2 ausgeschlossen werden soll, sowie den Endbenutzer an. Es wird verwendet, um die Empfehlungsergebnisse zu präsentieren.

―― Danach werden wir mit der Diskussion fortfahren, indem wir davon ausgehen, dass die Elemente der Liste vom Typ Integer sind, aber nicht auf den Typ Integer beschränkt sind, und es gibt kein Problem, selbst wenn es kompliziert ist wie `List <String>`.

• Jede Liste darf keine doppelten Elemente enthalten. (Aus praktischer Sicht sollten Sie berücksichtigen, dass eine solche Duplizierung beseitigt ist, bevor die Methode aufgerufen wird.)

Collection#removeAll Die erste Methodenimplementierung, die ich mir ausgedacht habe, war:

1st

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

Es ist übersichtlich und leicht zu lesen, aber es ist weniger wünschenswert, weil Sie die Argumente geändert haben. Es ist möglich, die Liste mit der Methode `` `clone``` zu kopieren, aber diesmal werden wir eine andere Methode in Betracht ziehen.

Eine andere Richtung: Java 8 Stream API

Betrachten Sie die folgende Implementierung mit der in Java 8 eingeführten Stream-API. list1Über die Elemente inlist2Wenn nicht enthalten, das ErgebnisresultlistIch werde es hinzufügen.

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

Es wird wahrscheinlich auch einige Verbesserungen bei dieser Implementierung geben.

-- `new ArrayList <> (); Sie können das Ergebnis von list1.stream () `an resultListübergeben, ohne eine neue Instanz mit` zu erstellen.

• Um die Methode `.contains ()` in einer Liste aufzurufen, muss O (n) (Java 8 streamt, wie Inhalte einer Liste gefiltert werden, die nicht in einer anderen gefunden wurde. Anordnungsliste? )

In Bezug auf den zweiten Punkt wird in der obigen Implementierung "list2.contains ()" für jedes Element von "list1" aufgerufen, also insgesamt "O (n)". ^ 2) Es wird notwendig sein, `zu verarbeiten. ([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) können Sie sehen, dass .contains () `` jedem Element einzeln folgt.)

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    }

Dritte Ehrlichkeit: .contains () für Set

Betrachten Sie die folgende Implementierung, die die obigen Punkte verbessert. Unter Verwendung von `.contains ()` für Set ist die Verarbeitung des Teils, der bestimmt, ob das Element von list1``` in` `list2``` enthalten ist,` O (1) Ich konnte es auf `` `unterdrücken.

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

Apropos

In Apache Commons Collections, [ListUtils.java](https://commons.apache.org/proper/commons- In Sammlungen / apidocs / src-html / org / apache / commons / collection4 / ListUtils.html) ist die Methode `` `subtrahieren``` wie folgt definiert.

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    }