Supprimer d'un HashSet échouant après l'avoir parcouru

Question

Je suis en train d'écrire un algorithme de clustering agglomératif dans Java et j'ai des problèmes avec une opération de suppression. Il semble toujours échouer lorsque le nombre de grappes atteint la moitié du nombre initial. Dans l'exemple de code ci-dessous, clusters est .

 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) finalement retourne faux, mais je ne comprends pas pourquoi.

J'ai testé ce code en créant d'abord 10 clusters, chacun avec un entier de 1 à 10. Les distances sont des nombres aléatoires entre 0 et 1. Voici la sortie après avoir ajouté quelques instructions println. Après le nombre de clusters, j'imprime les clusters réels, 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'le [10, 9, 5, 6, 4, 5, 6, 4, ...] réglé pousse simplement infiniment à partir de là.

Edit: pour clarifier, j'utilise un 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), elle n'est pas nécessairement dans la bonne position et les codes de hachage seront mis en cache. Vous devez l'enlever, le modifier, puis le réinsérer.

Answer 2

Le problème évident est que il clusters.remove utilise probablement equals pour trouver l'élément à supprimer Malheureusement equals.. sur les collections en général compare 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>()) (I pense).

Answer 3

Dans le test illustré, le remove échoue la première fois que vous tentez de supprimer une collection contenant plusieurs entiers. Est-ce toujours le cas?

Quel type de béton est utilisé pour la collection?