Was ist der Unterschied zwischen ArrayList.clear () und ArrayList.removeAll ()?

283

Angenommen, dies arraylistist definiert als ArrayList<String> arraylist, ist arraylist.removeAll(arraylist)äquivalent zu arraylist.clear()?

Wenn ja, kann ich davon ausgehen, dass die clear()Methode zum Leeren der Array-Liste effizienter ist?

Gibt es irgendwelche Einschränkungen bei der Verwendung arraylist.removeAll(arraylist)anstelle von arraylist.clear()?

ateiob
quelle
Eine mögliche Folge dieser Frage: Wann könnte eine anstelle der anderen verwendet werden?
Corey Ogburn
3
@Corey: Wann könnte jeder verwenden wollen arraylist.removeAll(arraylist)? Ich sehe absolut keinen Grund dazu.
Joachim Sauer
@ Joachim Sauer Genau das wollte ich überprüfen. Danke +2. Aber ist der Unterschied zwischen elementData[i] = nullund e.remove()signifikant?
Ateiob
Es gibt keinen vernünftigen Grund zu tun , arrList.removeAll(arrList)statt arrList.clear(). arrList1.removeAll(arrList2)ist eine andere Sache.
Vlad
3
Wenn nur die Implementierung von removeAll () mit dieser Zeile begonnen hätte, hätte diese ganze Diskussion viel unterhaltsamer sein können !!! if (c == this && !isEmpty()) { clear(); return true; }. Ich muss dies als Patch bei OpenJDK einreichen! ;-)
Julius Musseau

Antworten:

396

Der Quellcode für clear():

public void clear() {
    modCount++;

    // Let gc do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

Der Quellcode für removeAll()(wie in definiert AbstractCollection):

public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    Iterator<?> e = iterator();
    while (e.hasNext()) {
        if (c.contains(e.next())) {
            e.remove();
            modified = true;
        }
    }
    return modified;
}

clear() ist viel schneller, da es nicht mit all diesen zusätzlichen Methodenaufrufen umgehen muss.

Und wie Atrey betont, c.contains(..)erhöht sich die zeitliche Komplexität von removeAllO (n 2 ) im Gegensatz zu clearO (n).

Jeffrey
quelle
29
Ein Hinweis, der c.contains(...)die zeitliche Komplexität der Operation quadriert, würde diese Antwort vervollständigen.
Atreys
8
Die Quelle ist stark in diesem. (Zu allen anderen Antworten: Verwenden Sie die Quelle, Luke.) Beachten Sie, wie klar () als nur eine Zeile implementiert werden kann, Größe = 0; Aber Garbage-Collection würde nicht wissen, wie man die Elemente in den nicht erreichbaren Teilen des Arrays sammelt.
Julius Musseau
2
e.remove () ist viel komplexer! e.remove () quadriert ebenso die Komplexität wie c.contains (...). In einer ArrayList ruft e.remove () ArrayList.remove (int index) auf, wodurch der Rest des Arrays um eins verschoben werden muss.
Julius Musseau
1
@ateiob e.remove () ist zwei zusätzliche Methodenaufrufe, eine Bereichsprüfung und eine AbstractList.Itr.remove()ArrayList.remove(int)
Objektrückgabe
2
@julius Wenn dies size = 0; elementData = new Object[10];der Fall wäre : Der Rest wäre Müll, da das Hintergrundarray keine externen Referenzen enthält.
CorsiKa
51

Die zeitliche Komplexität von ArrayList.clear()ist O(n)und vonremoveAll istO(n^2) .

Also ja, ArrayList.clearist viel schneller.

Geoff
quelle
15

Die clear()Methode entfernt alle Elemente einer einzelnen ArrayList. Es ist eine schnelle Operation, da nur die Array-Elemente auf gesetzt werdennull .

Die removeAll(Collection)Methode, von der geerbt wird AbstractCollection, entfernt alle Elemente in der Argumentauflistung aus der Auflistung, für die Sie die Methode aufrufen. Es ist ein relativ langsamer Vorgang, da eine der beteiligten Sammlungen durchsucht werden muss.

Ernest Friedman-Hill
quelle
Ich dachte, es setzt einfach alles, nicht einige Elemente auf null. Wenn dies nicht der Fall ist, wie wurde entschieden, welche Elemente auf null gesetzt werden sollen?
Farid
2
@Farid sorry, mein Englisch ist hier einfach zu informell. Ich habe in der Tat gemeint, dass alle Elemente auf null gesetzt werden. Ich werde es reparieren!
Ernest Friedman-Hill
7

Sofern es keine spezifische Optimierung gibt, die prüft, ob das übergebene Argument removeAll()die Sammlung selbst ist (und ich bezweifle sehr , dass eine solche Optimierung vorhanden ist), ist sie erheblich langsamer als eine einfache.clear() .

Abgesehen davon (und mindestens genauso wichtig): arraylist.removeAll(arraylist)ist nur stumpfer, verwirrender Code. Es ist eine sehr rückständige Art zu sagen, "diese Sammlung löschen". Welchen Vorteil hätte es gegenüber dem sehr Verständlichen arraylist.clear() ?

Joachim Sauer
quelle
7

Sie dienen verschiedenen Zwecken. clear()Löscht eine Instanz der Klasse, removeAll()entfernt alle angegebenen Objekte und gibt den Status der Operation zurück.

lucapette
quelle
Können Sie bitte eine Ressource zur Verfügung stellen, um die oben genannte Angelegenheit als weitere Referenz zu lesen
Kasun Siyambalapitiya
1
@ KasunSiyambalapitiya Wie wäre es mit der akzeptierten Antwort , die den Quellcode für die beiden enthält?
Abdul
5

clear() geht das zugrunde liegende Array durch und setzt jeden Eintrag auf null;

removeAll(collection)Durchläuft die ArrayList und prüft remove(Object), ob eine Sammlung vorhanden ist.

Ich würde mir vorstellen, dass clear()das viel schneller ist als removeAll, weil es nicht vergleichbar ist usw.

Nikolaus
quelle
2

Das Löschen ist schneller, da die zu löschenden Elemente nicht durchlaufen werden. Diese Methode kann davon ausgehen, dass ALLE Elemente gelöscht werden können.

Remove allbedeutet nicht unbedingt, dass alle Elemente in der Liste gelöscht werden, sondern nur die als Parameter angegebenen Elemente sollten gelöscht werden. Daher sind weitere Anstrengungen erforderlich, um diejenigen zu behalten, die nicht gelöscht werden sollten.

KLÄRUNG

Mit 'Schleife' meine ich, dass nicht geprüft werden muss, ob das Element beibehalten werden soll oder nicht. Es kann die Referenz auf setzennull ohne die bereitgestellten Listen der zu löschenden Elemente zu durchsuchen.

ClearIST schneller als deleteall.

Jérôme Verstrynge
quelle
1
Ich bin mir ziemlich sicher, dass ArrayList.clear()das auch eine Schleife sein muss.
Joachim Sauer
@JVerstry Meinst du, dass clear () die Elemente, die es aus der ArrayList entfernt, nicht löscht ?
Ateiob
1
Falsch, klar durchläuft das interne Array und setzt alle Verweise auf null, damit der Garbage Collector seine Arbeit erledigen kann.
Devconsole
1
@Joachim, @devconsole: Ich denke, er meinte, es muss nicht die als Parameter angegebene Liste durchlaufen. target.removeAll(param)wird durchlaufen paramund dann aufrufen, target.contains(...)was wiederholt wird target.
Vlad
2
-3 ist ein bisschen hart. Wenn JVerstry wollte, konnte er seine eigene Java-Implementierung von Grund auf neu schreiben, die keine Schleife durchführte. clear () kann in O (1) ohne Schleife implementiert werden, während removeAll () eine Art O (n) -Algorithmus haben MUSS. Es gibt keine Möglichkeit, den Vertrag der removeAll () -API zu erfüllen, ohne alle Elemente zu untersuchen.
Julius Musseau
1

clear () wird viel effizienter sein. Es wird einfach jeden einzelnen Gegenstand entfernen. Die Verwendung von removeAll (Arraylist) erfordert viel mehr Arbeit, da jedes Element in der Arraylist überprüft wird, um festzustellen, ob es in der Arraylist vorhanden ist, bevor es entfernt wird.

CDelaney
quelle
-8

Array => Sobald der Speicherplatz zur Laufzeit einer Array-Variablen zugewiesen wurde, kann der zugewiesene Speicherplatz nicht erweitert oder entfernt werden.

ArrayList => Dies ist in Arraylist nicht der Fall. ArrayList kann zur Laufzeit wachsen und schrumpfen. Der zugewiesene Speicherplatz kann zur Laufzeit minimiert oder maximiert werden.

Arun Kumar
quelle
Dies beantwortet nicht die Frage, die den Unterschied zwischen ArrayList.clear () und ArrayList.removeAll () darstellt, nicht den Unterschied zwischen einem Array und einer ArrayList.
Pierre
Diese Antwort ist nicht erforderlich. Darum geht es in der Frage nicht.
Serafim Costa