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.
java
performance
for-loop
hashset
davidSC
la source
la source
for val
boucle est la chose qui prend le temps. C'estremove
encore très rapide. Une sorte de surcharge configurant un nouvel itérateur après la modification de l'ensemble ...?for val
boucle 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érifierhashSet.size() > 1 || !hashSet.contains(-1)
.Réponses:
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:
async-profiler montre que presque tout le temps est passé à l'intérieur du
java.util.HashMap$HashIterator()
constructeur:La ligne en surbrillance est une boucle linéaire qui recherche le premier compartiment non vide dans la table de hachage.
Puisque
Integer
a le trivialhashCode
(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
HashIterator
besoin de trouver le premier compartiment non vide.Essayez de retirer les clés de l'autre extrémité:
L'algorithme deviendra considérablement plus rapide!
la source
if (i % 800 == 0) { hashSet = new HashSet<>(hashSet); }
.