Nehmen Sie von der HashSet andernfalls nach über sie iterieren

Question

Ich schreibe einen Agglomerations Clustering-Algorithmus in Java und Problemen mit einer Entfernungsoperation. Es scheint immer fehlschlagen, wenn die Anzahl der Cluster Hälfte die ursprüngliche Zahl erreicht.

In dem folgenden Beispielcode, clusters ist ein 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);
      }

Nach einigen Durchläufen durch die Schleife, clusters.remove(minclust2) schließlich false zurück, aber ich verstehe nicht, warum.

I getestet diesen Code, indem zunächst 10 Cluster zu schaffen, die jeweils mit einer ganzen Zahl von 1 bis 10. Die Entfernungen sind Zufallszahlen zwischen 0 und 1. Hier ist das Ausgangssignal nach ein paar println Anweisungen hinzufügen. Nach der Anzahl der Cluster, drucke ich die tatsächlichen Cluster aus, die Zusammenführung und das Ergebnis 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

Den die [10, 9, 5, 6, 4, 5, 6, 4, ...] Set wächst nur unendlich von dort.

Edit:. Zu klären, ich bin in Clustern eine HashSet<Integer> für jeden Cluster mit (a HashSet<HashSet<Integer>>)

Answer 1

Ah. Wenn Sie einen Wert ändern, die bereits in einem Set (oder einem Map-Taste), dann ist es nicht unbedingt in der richtigen Position und Hash-Codes zwischengespeichert wird. Sie müssen sie entfernen, ändern sie und sie dann wieder ein.

Answer 2

Im Test gezeigt, schlägt die remove das erste Mal, wenn Sie versuchen, eine Sammlung zu entfernen mehr als eine Integer enthält. Ist das immer der Fall?

Was ist die konkrete Art der Sammlung verwendet?

Answer 3

Das offensichtliche Problem ist, dass clusters.remove wahrscheinlich equals wird mit dem Element finden zu entfernen. Leider vergleicht equals auf Sammlungen im Allgemeinen, ob die Elemente gleich sind, eher, als wenn sie die gleiche Sammlung ist (ich glaube, C # eine bessere Wahl in dieser Hinsicht macht).

eine einfache Lösung ist clusters als Collections.newSetFromMap(new IdentityHashMap<Collection<Integer>, Boolean>()) zu schaffen (glaube ich).