Metoda HashSet <T> .removeAll jest zaskakująco wolna

92

Jon Skeet niedawno poruszył na swoim blogu interesujący temat dotyczący programowania: „W mojej abstrakcji, droga Lizo, droga Lizo” (wyróżnienie dodane):

Mam zestaw - HashSetwłaściwie. Chcę usunąć z niego niektóre elementy… a wiele z nich może nie istnieć. W rzeczywistości w naszym przypadku testowym żaden element z kolekcji „do usunięcia” nie będzie w oryginalnym zestawie. Brzmi to - i rzeczywiście jest - niezwykle łatwe do zakodowania. W końcu musimy Set<T>.removeAllnam pomóc, prawda?

Określamy rozmiar zestawu „source” i rozmiar kolekcji „removals” w wierszu poleceń i budujemy oba z nich. Zbiór źródłowy zawiera tylko nieujemne liczby całkowite; zestaw usunięcia zawiera tylko ujemne liczby całkowite. Mierzymy, ile czasu zajmuje usunięcie wszystkich elementów za pomocą System.currentTimeMillis(), który nie jest najdokładniejszym stoperem na świecie, ale jest więcej niż wystarczający w tym przypadku, jak zobaczysz. Oto kod:

import java.util.*;
public class Test 
{ 
    public static void main(String[] args) 
    { 
       int sourceSize = Integer.parseInt(args[0]); 
       int removalsSize = Integer.parseInt(args[1]); 
        
       Set<Integer> source = new HashSet<Integer>(); 
       Collection<Integer> removals = new ArrayList<Integer>(); 
        
       for (int i = 0; i < sourceSize; i++) 
       { 
           source.add(i); 
       } 
       for (int i = 1; i <= removalsSize; i++) 
       { 
           removals.add(-i); 
       } 
        
       long start = System.currentTimeMillis(); 
       source.removeAll(removals); 
       long end = System.currentTimeMillis(); 
       System.out.println("Time taken: " + (end - start) + "ms"); 
    }
}

Zacznijmy od łatwego zadania: zestaw źródłowy zawierający 100 elementów i 100 do usunięcia:

c:UsersJonTest>java Test 100 100
Time taken: 1ms

Okay, więc nie spodziewaliśmy się, że będzie wolny… oczywiście możemy trochę przyspieszyć. Co powiesz na źródło miliona i 300 000 elementów do usunięcia?

c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms

Hmm. To wciąż wydaje się dość szybkie. Teraz czuję, że byłem trochę okrutny, prosząc go o usunięcie wszystkich. Ułatwmy to trochę - 300 000 elementów źródłowych i 300 000 usunięć:

c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms

Przepraszam? Prawie trzy minuty ? Yikes! Z pewnością powinno być łatwiej usuwać pozycje z mniejszej kolekcji niż ta, którą udało nam się w 38 ms?

Czy ktoś może wyjaśnić, dlaczego tak się dzieje? Dlaczego HashSet<T>.removeAllmetoda jest tak powolna?

Społeczność
źródło
2
Przetestowałem Twój kod i szybko zadziałał. W twoim przypadku zajęło to ~ 12 ms. Zwiększyłem również obie wartości wejściowe o 10 i zajęło to 36 ms. Może Twój komputer wykonuje intensywne zadania procesora podczas przeprowadzania testów?
Slimu
4
Przetestowałem to i uzyskałem ten sam wynik co OP (cóż, zatrzymałem go przed końcem). Rzeczywiście dziwne. Windows, JDK 1.7.0_55
JB Nizet
2
Jest na to otwarty bilet: JDK-6982173
Haozhun
44
Jak omówiono na Meta , to pytanie zostało pierwotnie plagiatowane z bloga Jona Skeeta (obecnie cytowane bezpośrednio i linkowane w pytaniu, ze względu na edycję moderatora). Przyszli czytelnicy powinni zauważyć, że wpis na blogu, z którego został on plagiatowany, faktycznie wyjaśnia przyczynę tego zachowania, podobnie jak przyjęta tutaj odpowiedź. W związku z tym zamiast czytać odpowiedzi tutaj, możesz po prostu kliknąć i przeczytać cały wpis na blogu .
Mark Amery
1
Błąd zostanie naprawiony w Javie 15: JDK-6394757
ZhekaKozlov

Odpowiedzi:

139

Zachowanie jest (nieco) udokumentowane w javadoc :

Ta implementacja określa, która jest mniejsza z tego zestawu i określonej kolekcji, wywołując metodę size na każdym z nich. Jeśli ten zestaw ma mniej elementów , implementacja wykonuje iterację po tym zestawie, sprawdzając po kolei każdy element zwracany przez iterator, aby sprawdzić, czy znajduje się w określonej kolekcji . Jeśli jest tak zawarty, jest usuwany z tego zestawu za pomocą metody usuwania iteratora. Jeśli określona kolekcja ma mniej elementów, implementacja wykonuje iterację po określonej kolekcji, usuwając z tego zestawu każdy element zwracany przez iterator przy użyciu metody remove tego zestawu.

Co to oznacza w praktyce, kiedy dzwonisz source.removeAll(removals);:

  • jeśli removalskolekcja ma mniejszy rozmiar niż source, wywoływana jest removemetoda HashSet, która jest szybka.

  • jeśli removalskolekcja ma rozmiar równy lub większy niż the source, to removals.containsjest wywoływana, co jest powolne dla ArrayList.

Szybka naprawa:

Collection<Integer> removals = new HashSet<Integer>();

Zauważ, że istnieje otwarty błąd, który jest bardzo podobny do tego, co opisujesz. Wydaje się, że jest to prawdopodobnie zły wybór, ale nie można go zmienić, ponieważ jest udokumentowany w javadoc.


Dla porównania, to jest kod removeAll(w Javie 8 - nie sprawdzałem innych wersji):

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;

    if (size() > c.size()) {
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}
asylias
źródło
15
Łał. Nauczyłem się czegoś dzisiaj. To wygląda na zły wybór implementacji. Nie powinni tego robić, jeśli druga kolekcja nie jest zestawem.
JB Nizet
2
@JBNizet Tak, to dziwne - zostało to omówione tutaj z twoją sugestią - nie wiem, dlaczego nie przeszło ...
assylias
2
Wielkie dzięki @assylias .. Ale naprawdę zastanawiam się, jak to rozgryzłeś ... :) Fajnie, naprawdę fajnie .... Czy napotkałeś ten problem ???
8
@show_stopper Właśnie uruchomiłem profilera i zobaczyłem, że to ArrayList#containsbył winowajca. Spojrzenie na kod AbstractSet#removeAlldało resztę odpowiedzi.
asylias