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 -
HashSet
wł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 musimySet<T>.removeAll
nam 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>.removeAll
metoda jest tak powolna?
źródło
Odpowiedzi:
Zachowanie jest (nieco) udokumentowane w javadoc :
Co to oznacza w praktyce, kiedy dzwonisz
source.removeAll(removals);
:jeśli
removals
kolekcja ma mniejszy rozmiar niżsource
, wywoływana jestremove
metodaHashSet
, która jest szybka.jeśli
removals
kolekcja ma rozmiar równy lub większy niż thesource
, toremovals.contains
jest 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; }
źródło
ArrayList#contains
był winowajca. Spojrzenie na kodAbstractSet#removeAll
dało resztę odpowiedzi.