Metoda HashSet removeAll jest zaskakująco powolna

Question

Metoda HashSet removeAll jest zaskakująco powolna

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

Określam rozmiar zestawu "source" i rozmiar kolekcji "removals" w wierszu poleceń i buduję oba. Zestaw źródłowy zawiera tylko nieujemne liczby całkowite; zestaw usuwania zawiera tylko ujemne liczby całkowite. Mierzę, jak długo trwa usunięcie wszystkich elementów za pomocą systemu.currentTimeMillis(), który nie jest światem najbardziej dokładny stoper, ale jest więcej niż odpowiedni 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 składający się ze 100 elementów i 100 do usunięcia:

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

Tak szybko, jak się spodziewałem.

Następnie próbowałem źródła milion elementów i 300,000 elementów do usunięcia?

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

To wciąż wydaje się dość szybkie. Teraz zrób to trochę łatwiej – 300 000 pozycji źródłowych i 300 000 usunięć:

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

Prawie trzy minuty?

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

65

java performance hashset

Author: Show Stopper, 2015-02-23

Source

1 answers

score 80 · Accepted Answer

Zachowanie jest (nieco) udokumentowane w javadoc :

Ta implementacja określa, który jest mniejszy z tego zbioru i określonego zbioru, wywołując metodę size na każdym z nich. Jeśli ten zestaw zawiera mniej elementów, następnie implementacja iteruje nad tym zestawem, sprawdzając po kolei każdy element zwracany przez iterator, aby zobaczyć jeśli jest zawarta w określonym zbiorze. Jeśli jest tak zawarta, to jest usunięte z tego zestawu za pomocą metody usuwania iteratora. Jeśli określona Kolekcja zawiera mniej elementów, wtedy implementacja iterauje nad określoną kolekcją, usuwając z tego zestawu każdy element zwrócony przez iterator, używając metody remove tego zestawu.

Co to oznacza w praktyce, gdy wywołujesz source.removeAll(removals);:

Jeśli zbiór removals ma mniejszy rozmiar niż source, wywoływana jest metoda remove z HashSet, która jest szybka.
Jeśli zbiór removals jest równy lub większy od source, wtedy wywoływany jest removals.contains, co jest powolne dla ArrayList.

Quick fix:

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

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

W celach informacyjnych jest to kod removeAll (w Javie 8 - nie sprawdzałem innych wersje):

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