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.
java
performance
for-loop
hashset
davidSC
źródło
źródło
for val
to, że zajęcie czasu zajmuje pętla.remove
Jest wciąż bardzo szybko. Jakiś narzut związany z konfiguracją nowego iteratora po modyfikacji zestawu ...?for val
pę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 wydajniejszehashSet.size() > 1 || !hashSet.contains(-1)
.Odpowiedzi:
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:
async-profiler pokazuje, że prawie cały czas spędza się w
java.util.HashMap$HashIterator()
konstruktorze:Podświetlona linia to pętla liniowa, która wyszukuje pierwsze niepuste wiadro w tabeli skrótów.
Ponieważ
Integer
ma trywialnyhashCode
(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
HashIterator
trzeba znaleźć pierwsze niepuste segmenty.Spróbuj usunąć klucze z drugiego końca:
Algorytm będzie znacznie szybszy!
źródło
if (i % 800 == 0) { hashSet = new HashSet<>(hashSet); }
.