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

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?

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