HashSet removeAll metoda jest zadziwiająco powolna

Question

Mam zestaw - HashSet Chcę usunąć niektóre elementy z niego ... żaden z elementów w kolekcji "usunięcia" nie będzie w oryginalnym zestawie.

Określaję rozmiar zestawu "źródłowego" i wielkość kolekcji "usuwania" w wierszu poleceń i buduję oba. Zbiór źródłowy zawiera tylko nieujemne liczby całkowite; zestaw usunięć zawiera tylko ujemne liczby całkowite. Zmierzam, ile czasu potrzeba na usunięcie wszystkich elementów za pomocą System.currentTimeMillis(), który nie jest najdokładniejszym stoperem na świecie, ale w tym przypadku jest więcej niż wystarczający, 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 poprzez nadanie mu to łatwa praca: zestaw źródłem 100 sztuk i 100 w celu usunięcia:

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

Dobra, to szybko, jak się spodziewałem.

Następnie wypróbowałem źródło miliona przedmiotów i 300 000 przedmiotów do usunięcia?

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

To wciąż wydaje się dość szybkie. Teraz sprawiają, że nieco łatwiej - 300,000 pozycji źródłowych oraz 300.000 przeprowadzki:

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

Prawie trzy minuty?

Naprawdę zdezorientowany !! Czy ktoś może wyjaśnić, dlaczego tak się dzieje?

Answer 1

zachowanie się (nieco) udokumentowane w javadoc:

Realizacja ta określa, który jest mniejszy od tego zbioru, a określony zbiór przez wywoływanie metody wielkości na każdej z nich. Jeśli ten zestaw ma mniej elementów, to iteracje wdrożeniowe nad tym zestawem, sprawdzanie każdego elementu zwrócony przez iteracyjnej z kolei zobaczyć jeśli jest zawarta w określonej kolekcji. Jeśli jest tak zawarty, jest usuwany z tego zestawu za pomocą metody usuwania iteratora. Jeśli podana kolekcja zawiera mniej elementów, wówczas implementacja iteruje nad określoną kolekcją, usuwając z tego zestawu każdy element zwracany przez iterator, używając metody usuwania tego zestawu.

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

• jeśli zbiór removals jest z mniejszym rozmiarze niż source, metoda HashSetremove nazywa, który jest szybki.

• jeśli zbiór removals jest równy lub większy rozmiar niż source, następnie removals.contains nazywa, który jest wolny dla ArrayList.

Szybka poprawka:

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

Należy pamiętać, że istnieje an open bug, który jest bardzo podobny do tego, co można opisać. Najważniejsze wydaje się, że jest to prawdopodobnie zły wybór, ale nie można go zmienić, ponieważ jest on udokumentowany w javadoc.

---

Dla porównania, jest to kod removeAll (w Java 8 - nie zostały sprawdzone w innych wersjach):

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