Comment obtenir un élément de LinkedHashSet en Java?
Je suis à la recherche d'écrire du code que les partitions d'un ensemble donné en sous-ensembles disjoints. Par exemple, un ensemble de joueurs de football et nous partition en fonction de l'équipe à laquelle ils appartiennent. Je veux à la fin, une liste de représentants, c'est à dire un joueur de chaque équipe.
Tous les joueurs de football savent tous les autres joueurs de leur équipe, c'est très pertinent pour la complexité. Donc, mon idée sur la façon de le faire est comme suit (où set
est actuellement LinkedHashSet<T>
):
while (!set.isEmpty()) {
E e = set.iterator().next();
makeRepresentative(e);
set.remove(AllPlayersOnSameTeamAs(e));
}
Cependant, il se sent bizarre de construire un nouvel itérateur à chaque étape, le tout en boucle. Un LinkedHashSet est censé avoir une sorte de firstElement()
fonction interne (pour son LinkedList comportement), mais pour une raison que je ne trouve pas comment faire. J'ai aussi essayé une boucle foreach, à la place, mais qui a abouti à un java.util.ConcurrentModificationException
.
Comment suis-je censé faire cela correctement?
- Êtes-vous sûr un
Set
est ce que vous voulez? - Nope, c'est exactement la façon dont vous le faites. Votre code est tout simplement parfait. (Plus précisément, les itérateurs sont beaucoup moins cher que vous le pensez, il n'est donc pas une grosse affaire.)
- aurais-je (en général) mieux utiliser un HashSet ou un LinkedHashSet pour cela? Vous ne savez pas si cela en vaut la surcharge si je ne vais jamais au-delà de l'élément 1?
- Bâton avec
LinkedHashSet
de même.
Vous devez vous connecter pour publier un commentaire.
Après la lecture de votre modifier et de mieux comprendre, voici une solution qui pourrait vous intéresser:
Noter que, sans rien savoir de plus au sujet de la définition de "similaires", ce problème est par nature quadratique. La seule façon dont il pourrait être fait linéaire, ou sous-quadratique, c'est que si il y avait moyen de hachage des éléments similaires à la même clé. Dans ce cas, vous pouvez utiliser la deuxième stratégie ci-dessus, mais de modifier la
processed
de la structure et de la partie qui vérifie que la précédente éléments similaires pour être plus efficace (actuellement, cette étape est linéaire en le nombre de groupes semblables, ce qui pourrait être linéaire dans le total des éléments).En outre, tout ce qui est sous-quadratique va sûrement utiliser plus que d'être constamment en mémoire. Si vous voulez constante de la mémoire, c'est le meilleur que vous pouvez faire (et c'est quadratique du temps):
Noter que l'utilisation d'iter.remove() fixe les modifications simultanées problème que vous aviez auparavant.
Je le ferais en un seul passage, de garder la trace des équipes, je l'avais vu.