Remover de um HashSet falhando após Iterando sobre ele
-
09-09-2019 - |
Pergunta
Eu estou escrevendo um algoritmo de agrupamento aglomerativo em java e tendo problemas com uma operação de remoção. Parece sempre falham quando o número de clusters atinge metade do número inicial.
No código de exemplo abaixo, é um clusters
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);
}
Depois de algumas corridas através do loop, clusters.remove(minclust2)
, eventualmente, retorna falso, mas eu não entendo o porquê.
Eu testei este código, criando primeiro 10 clusters, cada um com um número inteiro de 1 a 10. As distâncias são números aleatórios entre 0 e 1. Aqui está a saída depois de adicionar algumas declarações println. Após o número de clusters, eu imprimir os clusters reais, a operação de fusão, e o resultado 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
A do [10, 9, 5, 6, 4, 5, 6, 4, ...] definido apenas cresce infinitamente de lá.
Editar:. Para esclarecer, eu estou usando um HashSet<Integer>
para cada cluster em clusters (a HashSet<HashSet<Integer>>)
Solução
Ah. Quando você altera um valor que já está em um Set
(ou uma chave Map
), então não é necessariamente os códigos de posição e hash certas serão armazenados em cache. Você precisa removê-lo, alterá-lo e, em seguida, insira-o novamente.
Outras dicas
No teste mostrado, o remove
falhar na primeira vez que você tentar remover uma coleção que contém mais de um Integer. É este sempre o caso?
Qual é o tipo concreto da coleção usado?
O problema óbvio que há que clusters.remove
provavelmente está usando equals
para encontrar o elemento para remover. Infelizmente equals
em coleções geralmente compara se os elementos são os mesmos, ao invés de se é a mesma coleção (eu acredito C # faz uma escolha melhor a este respeito).
AN reparo fácil é criar clusters
como Collections.newSetFromMap(new IdentityHashMap<Collection<Integer>, Boolean>())
(eu acho).