Nieoczekiwany czas działania kodu HashSet

28

Więc pierwotnie miałem ten kod:

import java.util.*;

public class sandbox {
    public static void main(String[] args) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < 100_000; i++) {
            hashSet.add(i);
        }

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100_000; i++) {
            for (Integer val : hashSet) {
                if (val != -1) break;
            }

            hashSet.remove(i);
        }

        System.out.println("time: " + (System.currentTimeMillis() - start));
    }
}

Uruchomienie zagnieżdżonych pętli na moim komputerze zajmuje około 4 sekund i nie rozumiem, dlaczego trwało to tak długo. Pętla zewnętrzna działa 100 000 razy, wewnętrzna pętla for powinna działać 1 raz (ponieważ każda wartość hashSet nigdy nie będzie wynosić -1), a usunięcie elementu z HashSet to O (1), więc powinno być około 200 000 operacji. Jeśli na sekundę wykonuje się zwykle 100 000 000 operacji, dlaczego mój kod zajmuje 4 sekundy?

Dodatkowo, jeśli linia hashSet.remove(i);jest skomentowana, kod zajmuje tylko 16ms. Jeśli wewnętrzna pętla for jest skomentowana (ale nie hashSet.remove(i);), kod zajmuje tylko 8ms.

davidSC
źródło
4
Potwierdzam twoje ustalenia. Mógłbym spekulować na temat przyczyny, ale mam nadzieję, że ktoś mądry opublikuje fascynujące wyjaśnienie.
khelwood
1
Wygląda na for valto, że zajęcie czasu zajmuje pętla. removeJest wciąż bardzo szybko. Jakiś narzut związany z konfiguracją nowego iteratora po modyfikacji zestawu ...?
khelwood
@apangin podał dobre wyjaśnienie w stackoverflow.com/a/59522575/108326, dlaczego for valpętla jest wolna. Pamiętaj jednak, że pętla wcale nie jest potrzebna. Jeśli chcesz sprawdzić, czy w zestawie są jakieś wartości inne niż -1, sprawdzenie byłoby znacznie wydajniejsze hashSet.size() > 1 || !hashSet.contains(-1).
markusk

Odpowiedzi:

32

Utworzyłeś krańcowy przypadek użycia HashSet, w którym algorytm sprowadza się do kwadratowej złożoności.

Oto uproszczona pętla, która trwa tak długo:

for (int i = 0; i < 100_000; i++) {
    hashSet.iterator().next();
    hashSet.remove(i);
}

async-profiler pokazuje, że prawie cały czas spędza się w java.util.HashMap$HashIterator()konstruktorze:

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
--->        do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

Podświetlona linia to pętla liniowa, która wyszukuje pierwsze niepuste wiadro w tabeli skrótów.

Ponieważ Integerma trywialny hashCode(tj. HashCode jest równy samej liczbie), okazuje się, że kolejne liczby całkowite zajmują głównie kolejne segmenty w tabeli skrótów: liczba 0 idzie do pierwszego segmentu, liczba 1 do drugiego segmentu itp.

Teraz usuwasz kolejne liczby od 0 do 99999. W najprostszym przypadku (gdy segment zawiera pojedynczy klucz) usunięcie klucza jest realizowane jako zerowanie odpowiedniego elementu w tablicy segmentu. Pamiętaj, że tabela nie jest zagęszczana ani zmieniana po usunięciu.

Im więcej kluczy usuniesz z początku tablicy segmentu, tym dłużej HashIteratortrzeba znaleźć pierwsze niepuste segmenty.

Spróbuj usunąć klucze z drugiego końca:

hashSet.remove(100_000 - i);

Algorytm będzie znacznie szybszy!

apangin
źródło
1
Achh, natknąłem się na to, ale odrzuciłem to po kilku pierwszych uruchomieniach i pomyślałem, że może to być pewna optymalizacja JIT i przeszedłem do analizy za pomocą JITWatch. Powinieneś najpierw uruchomić async-profiler. Cholera!
Adwait Kumar
1
Dość interesujące. Jeśli zrobisz coś jak następuje w pętli, przyspiesza go przez zmniejszenie rozmiaru wewnętrznej mapy: if (i % 800 == 0) { hashSet = new HashSet<>(hashSet); }.
Szary - TAK przestań być zły