Was ist effizienter : mit removeAll() oder mithilfe der folgenden HashMap Technik zu behalten, nur die geänderten Datensätze in eine ArrayList

Was Sie speichern können, die auf Komplexität, Sie könnten verlieren in Speicherzuordnung, so ist nicht unbedingt effizienter. Arrraylist verwendet etwas ähnliches, um eine in-place-Partitionierung-Algorithmus zu heruntergekommen die backing-array und test gegen die vergleichen.

Beim Vergleich es sieht einfach zu finden, den index des ersten Auftretens von einem match gegen den backing-array Object[]. Der Algorithmus verwaltet zwei Indizes, eine für die Iteration durch die backing-array und einem als Platzhalter für die Spiele. Im Fall einer übereinstimmung, es bewegt sich einfach den index auf der Rückseite array und führt Sie auf die nächste eingehende element; dies ist relativ Billig.

Kommt es zu einem Punkt, wo Sie feststellt, dass die eingehende Sammlung enthält nicht den Wert am aktuellen index in der backing-array es einfach überschreibt das element, wo das Letzte match trat mit dem element am aktuellen index, ohne dass eine neue Speicherzuweisung. Dieses Muster wird wiederholt, bis alle Elemente in der ArrayList wurde ein Vergleich mit der eingehenden Inkasso zugrunde, daher die Komplexität, die Sie sind besorgt über.

Zum Beispiel:
Betrachten Sie eine arraylist mit 1,2,4,5 und eine Sammlung 'C' mit 4,1, dass wir das match gegen; zu wollen, entfernen Sie 4 und 1. hier ist jeder iteration auf die for-Schleife, das würde gehen 0 -> 4

Iteration: r ist die for-Schleife den index auf arraylist ein for (; r < size; r++)

r = 0 (nicht C enthalten 1? Ja, fahren Sie mit dem nächsten)
A: 1,2,4,5 w = 0

r = 1 (Nicht C enthalten 2? Nein, kopieren Sie den Wert in r in dem spot gezeigt, durch w++)
A: 2,2,4,5 w=1

r = 2 (Nicht C enthalten 4?, Ja überspringen)
A: 2,2,4,5 w=1

r = 3 (Keine C-5 enthalten? Nein, kopieren Sie den Wert in r in dem spot gezeigt, durch w++)

A: 2,5,4,5 w=2

r=4, stop

Vergleichen Sie w, um die Größe der backing-array-4. Da sind Sie nicht gleich Null die Werte von w auf das Ende des Arrays, und setzen Sie die Größe.

A: 2,5 Größe von 2

Den eingebauten removeAll auch der Auffassung, dass die ArrayLists kann null enthalten. Sie könnten werfen eine NPE auf Rekord.getStudentId() in der Lösung oben. Schließlich removeAll schützt gegen Ausnahmen in der Vergleichs-Sammlung auf.enthält. wenn das passiert, nutzt es schließlich zu tun, eine native memcopy schützt die Unterlage array von Korruption in einer hoch effizienten Art und Weise.

Dem ich begegnet bin, einem performance-Engpass in den removeAll in einigen Fällen (EMF-Modell manipulation Verwandte). Für ArrayList wie die oben genannten, verwenden Sie einfach standard -removeAll, aber wenn Ein ist beispielsweise ein EList, n^2 auftreten können.

Daher vermeiden, sich auf verborgene gute Eigenschaften von bestimmten Implementierungen List< T > ; Set.contains() O(1) eine Garantie (wenn Sie HashSet und haben eine anständige hashCode, log2(n) - für TreeSet Zusammenhang mit der Bestellung), verwenden, um gebunden Algorithmische Komplexität.

Ich den folgenden code verwenden, vermeidet sinnlose Kopien; die Absicht ist, dass Sie zum Scannen eine Datenstruktur, die die Suche irrelevante Elemente, die Sie nicht wollen, und indem Sie "todel".

Für einige Grund wie die Vermeidung von gleichzeitigen änderungen, die Sie navigieren in einem Baum etc..., können Sie entfernen von Elementen, wie Sie dies tun, aktualisiert. So, wir kumulieren, die Sie in ein HashSet "todel".

In der Funktion, das müssen wir ändern "container", da ist es in der Regel ein Attribut des Aufrufers, sondern mit remove(int index) auf "container" dazu bewegen könnten, eine Kopie, da der Links-Verschiebung der Elemente. Wir benutzen eine " kopieren "Inhalt" um dies zu erreichen.

Template-argument ist, da während der Auswahl-Prozess, bekomme ich oft Subtypen C, aber fühlen Sie sich frei zu verwenden < T > und das überall.

/**
 * Efficient O (n) operation to removeAll from an aggregation.
 * @param container a container for a set of elements (no duplicates), some of which we want to get rid of
 * @param todel some elements to remove, typically stored in a HashSet.
 */
public static <T> void removeAll ( List<T> container, Set<? extends T> todel ) {
    if (todel.isEmpty())
        return;
    List<T> contents = new ArrayList<T>(container);
    container.clear();
    //since container contains no duplicates ensure |B| max contains() operations
    int torem = todel.size();
    for (T elt : contents) {
        if ( torem==0 || ! todel.contains(elt) ) {
            container.add(elt);
        } else {
            torem--;
        }
    }
}

Also in deinem Fall würde man aufrufen mit : removeAll(A, new HashSet < C >(B));
Zahlung eine Kopie von B, wenn Sie wirklich können sich nicht ansammeln, in einen Satz< C > während der phase der Auswahl.

Legen Sie es in eine utility-Klasse und static-import für einfache Bedienung.