Also hatte ich ursprünglich diesen Code:
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));
}
}
Es dauert ungefähr 4 Sekunden, um die verschachtelten for-Schleifen auf meinem Computer auszuführen, und ich verstehe nicht, warum es so lange gedauert hat. Die äußere Schleife wird 100.000 Mal ausgeführt, die innere for-Schleife sollte 1 Mal ausgeführt werden (da jeder Wert von hashSet niemals -1 sein wird) und das Entfernen eines Elements aus einem HashSet ist O (1), sodass ungefähr 200.000 Operationen ausgeführt werden sollten. Wenn es normalerweise 100.000.000 Operationen in einer Sekunde gibt, warum dauert es 4 Sekunden, bis mein Code ausgeführt wird?
Wenn die Zeile hashSet.remove(i);
auskommentiert ist, dauert der Code nur 16 ms. Wenn die innere for-Schleife hashSet.remove(i);
auskommentiert ist (aber nicht ), dauert der Code nur 8 ms.
quelle
for val
Schleife die Zeit in Anspruch nehmen. Dasremove
ist immer noch sehr schnell. Eine Art Overhead beim Einrichten eines neuen Iterators, nachdem der Satz geändert wurde ...?for val
Schleife langsam ist. Beachten Sie jedoch, dass die Schleife überhaupt nicht benötigt wird. Wenn Sie überprüfen möchten, ob die Menge andere Werte als -1 enthält, ist die Überprüfung wesentlich effizienterhashSet.size() > 1 || !hashSet.contains(-1)
.Antworten:
Sie haben einen marginalen Anwendungsfall erstellt, bei
HashSet
dem sich der Algorithmus auf die quadratische Komplexität verschlechtert.Hier ist die vereinfachte Schleife, die so lange dauert:
Der Async-Profiler zeigt, dass fast die gesamte Zeit im
java.util.HashMap$HashIterator()
Konstruktor verbracht wird :Die hervorgehobene Zeile ist eine lineare Schleife, die nach dem ersten nicht leeren Bucket in der Hash-Tabelle sucht.
Da
Integer
das Triviale isthashCode
(dh hashCode ist gleich der Zahl selbst), stellt sich heraus, dass aufeinanderfolgende Ganzzahlen meistens die aufeinanderfolgenden Buckets in der Hash-Tabelle belegen: Nummer 0 geht an den ersten Bucket, Nummer 1 geht an den zweiten Bucket usw.Jetzt entfernen Sie die fortlaufenden Zahlen von 0 bis 99999. Im einfachsten Fall (wenn der Bucket einen einzelnen Schlüssel enthält) wird das Entfernen eines Schlüssels so implementiert, dass das entsprechende Element im Bucket-Array auf Null gesetzt wird. Beachten Sie, dass der Tisch nach dem Entfernen nicht verdichtet oder wieder aufgewärmt wird.
Je mehr Schlüssel Sie am Anfang des Bucket-Arrays entfernen, desto länger
HashIterator
muss der erste nicht leere Bucket gefunden werden.Versuchen Sie, die Schlüssel vom anderen Ende zu entfernen:
Der Algorithmus wird dramatisch schneller!
quelle
if (i % 800 == 0) { hashSet = new HashSet<>(hashSet); }
.