Retirer du défaut de HashSet après itérer dessus

Question

J'écris un algorithme de clustering agglomératif en Java et avoir des ennuis avec une opération de suppression. Il semble ne pas toujours quand le nombre de grappes atteint la moitié du nombre initial.

Dans l'exemple de code ci-dessous, clusters est un Collection<Collection<Integer>>.

      while(clusters.size() > K){
           // determine smallest distance between clusters
           Collection<Integer> minclust1 = null;
           Collection<Integer> minclust2 = null;
           double mindist = Double.POSITIVE_INFINITY;

           for(Collection<Integer> cluster1 : clusters){
                for(Collection<Integer> cluster2 : clusters){
                     if( cluster1 != cluster2 && getDistance(cluster1, cluster2) < mindist){
                          minclust1 = cluster1;
                          minclust2 = cluster2;
                          mindist = getDistance(cluster1, cluster2);
                     }
                }
           }

           // merge the two clusters
           minclust1.addAll(minclust2);
           clusters.remove(minclust2);
      }

Après quelques passages dans la boucle, clusters.remove(minclust2) retourne finalement faux, mais je ne comprends pas pourquoi.

Je l'ai testé ce code en créant d'abord 10 groupes, chacun avec un nombre entier de 1 à 10. Les distances sont des nombres aléatoires entre 0 et 1. Voici le résultat après avoir ajouté quelques instructions println. Après le nombre de grappes, imprimer les grappes réelles, l'opération de fusion, et le résultat de clusters.remove (minclust2).

Clustering: 10 clusters
[[3], [1], [10], [5], [9], [7], [2], [4], [6], [8]]
[5] <- [6]
true
Clustering: 9 clusters
[[3], [1], [10], [5, 6], [9], [7], [2], [4], [8]]
[7] <- [8]
true
Clustering: 8 clusters
[[3], [1], [10], [5, 6], [9], [7, 8], [2], [4]]
[10] <- [9]
true
Clustering: 7 clusters
[[3], [1], [10, 9], [5, 6], [7, 8], [2], [4]]
[5, 6] <- [4]
true
Clustering: 6 clusters
[[3], [1], [10, 9], [5, 6, 4], [7, 8], [2]]
[3] <- [2]
true
Clustering: 5 clusters
[[3, 2], [1], [10, 9], [5, 6, 4], [7, 8]]
[10, 9] <- [5, 6, 4]
false
Clustering: 5 clusters
[[3, 2], [1], [10, 9, 5, 6, 4], [5, 6, 4], [7, 8]]
[10, 9, 5, 6, 4] <- [5, 6, 4]
false
Clustering: 5 clusters
[[3, 2], [1], [10, 9, 5, 6, 4, 5, 6, 4], [5, 6, 4], [7, 8]]
[10, 9, 5, 6, 4, 5, 6, 4] <- [5, 6, 4]
false

l [10, 9, 5, 6, 4, 5, 6, 4, ...] réglé pousse simplement infiniment à partir de là.

Modifier. Pour clarifier, j'utilise un HashSet<Integer> pour chaque cluster en grappes (un HashSet<HashSet<Integer>>)

Answer 1

Ah. Lorsque vous modifiez une valeur qui est déjà dans une Set (ou une clé Map), alors il est pas nécessairement dans les codes de position droite et hachage sera mis en cache. Vous devez supprimer, modifier et puis re-insérer.

Answer 2

Dans le test montré, l'remove échoue la première fois que vous essayez de supprimer une collection contenant plus d'un entier. Est-ce toujours le cas?

Quel est le type concret de la collection utilisée?

Answer 3

Le problème évident est que il clusters.remove utilise probablement equals pour trouver l'élément à supprimer. Malheureusement equals collections compare généralement si les éléments sont les mêmes, plutôt que si elle est la même collection (je crois C # fait un meilleur choix à cet égard).

une solution facile est de créer clusters comme Collections.newSetFromMap(new IdentityHashMap<Collection<Integer>, Boolean>()) (je pense).