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.

InformationsquelleAutor user1111929 | 2012-09-12

1
```
while (!set.isEmpty()) {    
    Collection<E> toBeRemoved = new ArrayList<E>();
    E first = set.iterator().next();
    doSomethingWith(e);
    for (E e : set) {
        if (similar(first, e)) toBeRemoved.add(e);
    }
    set.removeAll(toBeRemoved);
}
```
Après la lecture de votre modifier et de mieux comprendre, voici une solution qui pourrait vous intéresser:
```
Collection<E> processed = new ArrayList<E>();
for (E e1 : set) {
    boolean similar = false;
    for (E e2 : processed) {
        if (similar(e1, e2)) similar = true;
    }
    if (!similar) {
        doSomethingWith(e1);
        processed.add(e1);
    }
}
set.clear();
```
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):
```
while (!set.isEmpty()) {
    Iterator<E> iter = set.iterator();
    E first = iter.next();
    doSomethingWith(first);
    while (iter.hasNext()) {
        if (similar(first, iter.next())) iter.remove();
    }
}
```
Noter que l'utilisation d'iter.remove() fixe les modifications simultanées problème que vous aviez auparavant.
- Et que, dans une boucle while? Sauf que je suis absent quelque chose d'évident, qui a quadratique de la complexité au lieu de linéaire... :/
- Pourquoi en serait-il dans une boucle while? En fait, maintenant que j'y pense, je ne suis pas sûr que je suis totalement clair sur la question d'origine. Pourquoi êtes-vous en boucle jusqu'à ce que le jeu est vide? Si vous faites cela, pourquoi ne pas le faire ensemble.clear()?
- J'ai édité mon post, j'espère que c'est clair maintenant? Apparemment, j'ai oublié de mentionner que j'ai aussi besoin de utilisation de l'élément e. En fait, mon jeu est divisé en sous-ensembles, et semblable se trouve dans le même sous-ensemble. Donc, je veux choisir un représentant de chaque sous-ensemble.
- Oui, merci, je comprends maintenant. J'ai édité avec une meilleure réponse.
InformationsquelleAutor Joe K

Je le ferais en un seul passage, de garder la trace des équipes, je l'avais vu.

Set<Team> processedTeams = new HashSet<>();
Set<Players> representatives = new HashSet<>();
for(e:players) {
  Team t = e.getTeam();
  if(processedTeams.contains(t))
    continue;
  processedTeams.add(t);
  representatives.add(e)
}

InformationsquelleAutor Michael Anderson

Vous devez vous connecter pour publier un commentaire.