Temps d'exécution inattendus pour le code HashSet

28

Donc à l'origine, j'avais ce 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));
    }
}

Il faut environ 4 secondes pour exécuter les boucles imbriquées sur mon ordinateur et je ne comprends pas pourquoi cela a pris autant de temps. La boucle externe s'exécute 100 000 fois, la boucle for interne doit s'exécuter 1 fois (car toute valeur de hashSet ne sera jamais -1) et la suppression d'un élément d'un HashSet est O (1), il devrait donc y avoir environ 200 000 opérations. S'il y a généralement 100 000 000 d'opérations en une seconde, comment se fait-il que mon code prenne 4 secondes pour s'exécuter?

De plus, si la ligne hashSet.remove(i);est mise en commentaire, le code ne prend que 16 ms. Si la boucle for interne est commentée (mais pas hashSet.remove(i);), le code ne prend que 8 ms.

davidSC
la source
4
Je confirme vos conclusions. Je pourrais spéculer sur la raison, mais j'espère que quelqu'un d'intelligent publiera une explication fascinante.
khelwood
1
On dirait que la for valboucle est la chose qui prend le temps. C'est removeencore très rapide. Une sorte de surcharge configurant un nouvel itérateur après la modification de l'ensemble ...?
khelwood
@apangin a fourni une bonne explication dans stackoverflow.com/a/59522575/108326 pour expliquer pourquoi la for valboucle est lente. Cependant, notez que la boucle n'est pas nécessaire du tout. Si vous souhaitez vérifier s'il existe des valeurs différentes de -1 dans l'ensemble, il serait beaucoup plus efficace de vérifier hashSet.size() > 1 || !hashSet.contains(-1).
Markusk

Réponses:

32

Vous avez créé un cas d'utilisation marginal de HashSet, où l'algorithme se dégrade en complexité quadratique.

Voici la boucle simplifiée qui prend tellement de temps:

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

async-profiler montre que presque tout le temps est passé à l'intérieur du java.util.HashMap$HashIterator()constructeur:

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

La ligne en surbrillance est une boucle linéaire qui recherche le premier compartiment non vide dans la table de hachage.

Puisque Integera le trivial hashCode(c'est-à-dire que hashCode est égal au nombre lui-même), il s'avère que les entiers consécutifs occupent principalement les compartiments consécutifs dans la table de hachage: le numéro 0 va au premier compartiment, le numéro 1 va au deuxième compartiment, etc.

Vous supprimez maintenant les nombres consécutifs de 0 à 99999. Dans le cas le plus simple (lorsque le compartiment contient une seule clé), la suppression d'une clé est implémentée en annulant l'élément correspondant dans le tableau de compartiments. Notez que la table n'est pas compactée ou remélangée après le retrait.

Ainsi, plus vous supprimez de clés depuis le début du tableau de compartiments, plus vous avez HashIteratorbesoin de trouver le premier compartiment non vide.

Essayez de retirer les clés de l'autre extrémité:

hashSet.remove(100_000 - i);

L'algorithme deviendra considérablement plus rapide!

apangin
la source
1
Ahh, je suis tombé sur cela, mais je l'ai rejeté après les premières exécutions et j'ai pensé que cela pourrait être une optimisation JIT et je suis passé à l'analyse via JITWatch. Doit avoir exécuté async-profiler en premier. Zut!
Adwait Kumar
1
Assez intéressant. Si vous faites quelque chose comme ce qui suit dans la boucle, il l' accélère en réduisant la taille de la carte intérieure: if (i % 800 == 0) { hashSet = new HashSet<>(hashSet); }.
Gray - Alors arrêtez d'être maléfique le