Jaka jest różnica między ArrayList.clear () a ArrayList.removeAll ()?

283

Zakładając, że arraylistjest zdefiniowane jako ArrayList<String> arraylist, jest arraylist.removeAll(arraylist)równoważne arraylist.clear()?

Jeśli tak, to czy mogę założyć, że clear()metoda jest bardziej wydajna w przypadku opróżniania listy tablic?

Czy istnieją jakieś zastrzeżenia dotyczące używania arraylist.removeAll(arraylist)zamiast arraylist.clear()?

ateiob
źródło
Możliwy następstwo tego pytania: kiedy można użyć jednego zamiast drugiego?
Corey Ogburn,
3
@Corey: kiedy każdy może chcieć używać arraylist.removeAll(arraylist)? Nie widzę absolutnie żadnego powodu, aby to robić.
Joachim Sauer,
@Jachachim Sauer Właśnie to chciałem zweryfikować. Dzięki +2. Ale czy różnica między elementData[i] = nulli e.remove()znacząca?
ateiob,
arrList.removeAll(arrList)Zamiast tego nie ma rozsądnego powodu arrList.clear(). arrList1.removeAll(arrList2)to inna sprawa.
Vlad
3
Gdyby tylko implementacja removeAll () rozpoczęła się od tego wiersza, cała ta dyskusja mogłaby być o wiele bardziej zabawna !!! if (c == this && !isEmpty()) { clear(); return true; }. Będę musiał przesłać to do OpenJDK jako poprawkę! ;-)
Julius Musseau,

Odpowiedzi:

396

Kod źródłowy dla clear():

public void clear() {
    modCount++;

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

    size = 0;
}

Kod źródłowy removeAll()(zgodnie z definicją w 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() jest znacznie szybszy, ponieważ nie musi obsługiwać wszystkich dodatkowych wywołań metod.

I jak podkreśla Atrey, c.contains(..)zwiększa złożoność czasową removeAlldo O (n 2 ) w przeciwieństwie do clearO (n).

Jeffrey
źródło
29
Uwaga, która c.contains(...)wyrówna złożoność czasową operacji, dopełniłaby tę odpowiedź.
Atreys
8
Źródło jest w tym mocne. (Do wszystkich innych odpowiedzi: Użyj źródła, Luke.) Zauważ, jak clear () można zaimplementować jako jedną linię, size = 0; ale odśmiecanie nie wiedziałoby, jak zbierać elementy w nieosiągalnych częściach tablicy.
Julius Musseau,
2
e.remove () jest znacznie bardziej złożony! e.remove () również podnosi złożoność, podobnie jak c.contains (...). Na ArrayList, e.remove () wywołuje ArrayList.remove (int index), który musi przesunąć resztę tablicy o jeden.
Julius Musseau,
1
@ateiob e.remove () to również dwa dodatkowe wywołania metod, sprawdzanie zasięgu i zwracanie obiektu (wewnętrzny do AbstractList.Itr.remove()i ArrayList.remove(int))
Atreys
2
@julius Gdyby to zrobił: size = 0; elementData = new Object[10];cała reszta byłaby śmieciami, ponieważ tablica podkładu nie ma zewnętrznych odwołań.
corsiKa
51

Złożoność czasowa ArrayList.clear()jest O(n)i removeAlljest O(n^2).

Tak, ArrayList.clearjest znacznie szybszy.

Geoff
źródło
15

clear()Sposób usuwa wszystkie elementy pojedyncze ArrayList. Jest to szybka operacja, ponieważ po prostu ustawia elementy tablicy null.

removeAll(Collection)Metoda, która jest dziedziczona od AbstractCollectionusuwa wszystkie elementy, które znajdują się w zbiorach argument z kolekcji wywołać metodę dalej. Jest to stosunkowo powolna operacja, ponieważ musi przeszukiwać jedną z zaangażowanych kolekcji.

Ernest Friedman-Hill
źródło
Myślałem, że po prostu ustawia wszystkie, a nie niektóre elementy na zero. Jeśli tak nie jest, w jaki sposób zdecydowano, które elementy powinny mieć wartość null?
Farid
2
@ Cholera, przepraszam, mój angielski jest tutaj zbyt nieformalny. Rzeczywiście miałem na myśli, że ustawia wszystkie elementy na zero. Naprawię to!
Ernest Friedman-Hill
7

O ile nie istnieje konkretna optymalizacja, która sprawdza, czy przekazanym argumentem removeAll()jest sama kolekcja (i bardzo wątpię, że taka optymalizacja istnieje), będzie ona znacznie wolniejsza niż prosta.clear() .

Poza tym (i co najmniej równie ważne): arraylist.removeAll(arraylist)jest po prostu tępy, mylący kod. Jest to bardzo odwrotny sposób powiedzenia „wyczyść tę kolekcję”. Jaką przewagę miałby nad bardzo zrozumiałym arraylist.clear() ?

Joachim Sauer
źródło
7

Służą do różnych celów. clear()czyści instancję klasy, removeAll()usuwa wszystkie podane obiekty i zwraca stan operacji.

lucapette
źródło
czy możesz podać źródło do przeczytania powyższej sprawy w celu
późniejszego wykorzystania
1
@KasunSiyambalapitiya A co z zaakceptowaną odpowiedzią , która zawiera kod źródłowy tych dwóch?
Abdul
5

clear() przejdzie przez podstawową tablicę i ustawi każdy wpis na zero;

removeAll(collection) przejdzie przez ArrayList sprawdzając kolekcję i remove(Object) jeśli istnieje.

Wyobrażam sobie, że clear()jest to o wiele szybsze niż removeAll, ponieważ nie ma porównania itp.

Mikołaj
źródło
2

Czyszczenie jest szybsze, ponieważ nie zapętla elementów do usunięcia. W tej metodzie można założyć, że WSZYSTKIE elementy można usunąć.

Remove allniekoniecznie oznacza usunięcie wszystkich elementów z listy, tylko te podane jako parametry POWINNY zostać usunięte. Dlatego konieczne są większe wysiłki, aby zachować te, których nie należy usuwać.

WYJAŚNIENIE

Przez „pętlę” rozumiem, że nie musi sprawdzać, czy element powinien zostać zachowany, czy nie. Może ustawić odniesienie donull bez przeszukiwania dostarczonych list elementów do usunięcia.

ClearJEST szybszy niż deleteall.

Jérôme Verstrynge
źródło
1
Jestem pewien, że to również ArrayList.clear()musi się zapętlić.
Joachim Sauer,
@JVerstry Czy masz na myśli, że clear () nie usuwa elementów, które usuwa z ArrayList?
ateiob,
1
Źle, clear nie zapętla wewnętrznej tablicy i ustawia wszystkie odwołania na null, aby umożliwić modułowi wyrzucania elementów bezużytecznych.
devconsole,
1
@Jachachim, @devconsole: Myślę, że miał na myśli, że nie będzie musiał zapętlać / iterować listy podanej jako parametr. target.removeAll(param)wykona iterację, parama następnie zadzwoni, target.contains(...)która iteracja się zakończy target.
Vlad
2
-3 jest nieco trudny. Gdyby chciał JVerstry, mógłby napisać od podstaw własną implementację Java, która nie zapętlała się. clear () można realnie zaimplementować w O (1), bez pętli, podczas gdy removeAll () MUSI mieć jakiś algorytm O (n), nie ma sposobu na spełnienie kontraktu API removeAll () bez zbadania wszystkich elementów.
Julius Musseau,
1

clear () będzie znacznie wydajniejszy. Po prostu usunie każdy element. Korzystanie z removeAll (arraylist) zajmie o wiele więcej pracy, ponieważ sprawdzi każdy element w arraylist, aby sprawdzić, czy istnieje on w arraylist przed usunięciem.

CDelaney
źródło
-8

Array => po przydzieleniu miejsca dla zmiennej Array w czasie wykonywania przydzielonej przestrzeni nie można rozszerzyć ani usunąć.

ArrayList => Nie jest tak w przypadku tablicy arraylist. ArrayList może rosnąć i kurczyć się w czasie wykonywania. Przydzielone miejsce można zminimalizować lub zmaksymalizować w czasie wykonywania.

Arun Kumar
źródło
To nie odpowiada na pytanie, jaka jest różnica między ArrayList.clear () i ArrayList.removeAll (), a nie różnica między ArrayList i ArrayList.
Pierre,
Ta odpowiedź jest niepotrzebna. Nie o to chodzi w tym pytaniu.
Serafim Costa