Je possède deux jeux, A et B, du même type.
Je dois trouver si A contient un élément de l'ensemble B.
Quelle serait la meilleure façon de le faire sans itérer sur les ensembles ? La bibliothèque Set possède contains(object) y containsAll(collection) mais pas containsAny(collection) .
N'est-ce pas ? Collections.disjoint(A, B) travail ? Dans la documentation :
Renvoie à
truesi les deux collections spécifiées n'ont aucun élément en commun.
Ainsi, la méthode renvoie false si les collections contiennent des éléments communs.
Je préfère cette solution aux autres car elle ne modifie aucun des ensembles et n'en crée pas de nouveau.
Il s'agit d'un JRE standard, qui fonctionne avec n'importe quelle collection, et pas seulement avec le jeu.
Je ne pense pas que ce soit le plus rapide, il ne court-circuite pas lorsque le premier élément de l'intersection est trouvé.
Une bonne façon d'implémenter containsAny pour les ensembles est d'utiliser l'outil Guava Sets.intersection() .
containsAny retournerait un boolean de sorte que l'appel ressemble à :
Sets.intersection(set1, set2).isEmpty()Cela renvoie vrai si les ensembles sont disjoints, sinon faux. La complexité temporelle de cette méthode est probablement légèrement meilleure que celle de retainAll, car vous n'avez pas à effectuer de clonage pour éviter de modifier votre ensemble original.
Le seul inconvénient de cette approche est que vous devez inclure les bibliothèques guava. Ce qui, à mon avis, n'est pas un inconvénient car les API de collecte de Google sont très solides.
@DidierL la plupart des fonctions utilitaires de Guava Collections, y compris celle-ci, retournent vues des structures de données. Il n'y a donc pas à s'inquiéter de la "construction de l'ensemble" dans ce cas. L'implémentation est intéressante à lire ici, et/ou voir la javadoc : google.github.io/guava/releases/21.0/api/docs/com/google/common/
@MohammadAdnan Un autre inconvénient est qu'il calcule l'intersection complète - si l'ensemble1 et l'ensemble2 sont très grands, cela serait beaucoup plus gourmand en ressources (à la fois en termes de CPU et de mémoire) que de simplement vérifier s'ils ont un élément en commun.
Si le but d'éviter l'itération est l'efficacité, retainAll ne va probablement pas aider. Sa mise en œuvre dans AbstractCollection itère.
Yshavit a raison. Étant donné que l'O.P. cherche à voir si cualquier élément existe dans les deux ensembles, un algorithme approprié aurait un O(1) dans le meilleur des cas, alors que retainAll aurait quelque chose de l'ordre d'un O(N) (cela dépendrait de la taille d'un seul ensemble) temps d'exécution dans le meilleur des cas.
Je recommande de créer un HashMap à partir de l'ensemble A, puis en itérant à travers l'ensemble B et en vérifiant si un élément de B se trouve dans A. Cela s'exécuterait en O(|A|+|B|) temps (puisqu'il n'y aurait pas de collisions), alors que retainAll(Collection<?> c) doit fonctionner dans O(|A|*|B|) temps.
Dans la plupart des cas, il est nécessaire de conserver l'ensemble d'origine. retainAll il est nécessaire de faire une copie de l'ensemble original. Il est alors plus efficace d'utiliser HashSet comme suggéré par Zéychin .
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
4 votes
Essayez-vous d'éviter l'itération pour des raisons d'efficacité ou de propreté du code ?