Удалить из HashSet не удалось после повторения по нему
-
09-09-2019 - |
Вопрос
Я пишу алгоритм агломеративной кластеризации в Java, и у меня возникли проблемы с операцией удаления.Кажется, что он всегда терпит неудачу, когда количество кластеров достигает половины первоначального числа.
В приведенном ниже примере кода 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);
}
После нескольких прогонов цикла clusters.remove(minclust2)
в конечном итоге возвращает false, но я не понимаю, почему.
Я протестировал этот код, сначала создав 10 кластеров, каждый из которых имеет одно целое число от 1 до 10.Расстояния представляют собой случайные числа от 0 до 1.Вот результат после добавления нескольких операторов println.После количества кластеров я распечатываю фактические кластеры, операцию слияния и результат groups.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
Набор [10, 9, 5, 6, 4, 5, 6, 4, ...] оттуда бесконечно растет.
Редактировать:чтобы уточнить, я использую HashSet<Integer>
для каждого кластера в кластерах (a HashSet<HashSet<Integer>>)
.
Решение
Ах.Когда вы изменяете значение, которое уже находится в Set
(или Map
ключ), то он не обязательно находится в правильном положении и хэш-коды будут кэшироваться.Вам нужно удалить его, изменить и затем снова вставить.
Другие советы
В показанном тесте remove
происходит сбой при первой попытке удалить коллекцию, содержащую более одного целого числа.Всегда ли это так?
Какой конкретный тип используемой коллекции?
Очевидная проблема заключается в том, что clusters.remove
вероятно, использует equals
чтобы найти элемент, который нужно удалить.К сожалению equals
в коллекциях обычно сравнивает, являются ли элементы одинаковыми, а не является ли это одной и той же коллекцией (я считаю, что C# делает лучший выбор в этом отношении).
Простое решение — создать clusters
как Collections.newSetFromMap(new IdentityHashMap<Collection<Integer>, Boolean>())
(Я думаю).