Unerwartete Laufzeiten für HashSet-Code

28

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.

davidSC
quelle
4
Ich bestätige Ihre Ergebnisse. Ich könnte über den Grund spekulieren, aber hoffentlich wird jemand, der klug ist, eine faszinierende Erklärung veröffentlichen.
Khelwood
1
Es sieht so aus, als würde die for valSchleife die Zeit in Anspruch nehmen. Das removeist immer noch sehr schnell. Eine Art Overhead beim Einrichten eines neuen Iterators, nachdem der Satz geändert wurde ...?
Khelwood
@apangin lieferte in stackoverflow.com/a/59522575/108326 eine gute Erklärung dafür, warum die for valSchleife 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 effizienter hashSet.size() > 1 || !hashSet.contains(-1).
Markusk

Antworten:

32

Sie haben einen marginalen Anwendungsfall erstellt, bei HashSetdem sich der Algorithmus auf die quadratische Komplexität verschlechtert.

Hier ist die vereinfachte Schleife, die so lange dauert:

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

Der Async-Profiler zeigt, dass fast die gesamte Zeit im java.util.HashMap$HashIterator()Konstruktor verbracht wird :

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

Die hervorgehobene Zeile ist eine lineare Schleife, die nach dem ersten nicht leeren Bucket in der Hash-Tabelle sucht.

Da Integerdas Triviale ist hashCode(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 HashIteratormuss der erste nicht leere Bucket gefunden werden.

Versuchen Sie, die Schlüssel vom anderen Ende zu entfernen:

hashSet.remove(100_000 - i);

Der Algorithmus wird dramatisch schneller!

Apangin
quelle
1
Ahh, ich bin darauf gestoßen, habe es aber nach den ersten Läufen verworfen und dachte, dies könnte eine JIT-Optimierung sein, und bin zur Analyse über JITWatch übergegangen. Sollte zuerst den Async-Profiler ausgeführt haben. Verdammt!
Adwait Kumar
1
Sehr interessant. Wenn Sie in der Schleife Folgendes tun, wird dies beschleunigt, indem die Größe der inneren Karte verringert wird : if (i % 800 == 0) { hashSet = new HashSet<>(hashSet); }.
Grau - Also hör auf böse zu sein