Un moyen simple de savoir si deux listes différentes contiennent exactement les mêmes éléments?

Quelle est la manière la plus simple de savoir si deux listes contiennent exactement les mêmes éléments, dans les bibliothèques Java standard?

Peu importe que les deux listes aient la même instance ou non, cela ne devrait pas avoir d’importance si le paramètre type des listes est différent.

par exemple

List list1 List list2; // ... construct etc list1.add("A"); list2.add("A"); // the function, given these two lists, should return true 

Il y a probablement quelque chose qui me regarde en face Je sais 🙂


EDIT: Pour clarifier, je cherchais les mêmes éléments EXACT et le nombre d’éléments, dans l’ordre.


EDIT: Merci d’avoir souligné la réponse évidente que je ne pouvais pas voir pour regarder 🙂

Bien que toutes les réponses données jusqu’ici soient correctes, certaines sont plus correctes que d’autres, alors j’attendrai la meilleure réponse arrondie avant d’accepter.

Si vous vous souciez de l’ordre, utilisez simplement la méthode des égaux:

 list1.equals(list2) 

Du javadoc:

Compare l’object spécifié avec cette liste pour l’égalité. Renvoie true si et seulement si l’object spécifié est également une liste, les deux listes ont la même taille et toutes les paires d’éléments correspondantes des deux listes sont égales. (Deux éléments e1 et e2 sont égaux si (e1 == null? E2 == null: e1.equals (e2)).) En d’autres termes, deux listes sont définies égales si elles contiennent les mêmes éléments dans le même ordre. . Cette définition garantit que la méthode equals fonctionne correctement sur différentes implémentations de l’interface List.

Si vous souhaitez vérifier indépendamment de l’ordre, vous pouvez copier tous les éléments dans Sets et utiliser les égaux sur les ensembles résultants:

 public static  boolean listEqualsIgnoreOrder(List list1, List list2) { return new HashSet<>(list1).equals(new HashSet<>(list2)); } 

Une des limites de cette approche est qu’elle n’ignore pas seulement l’ordre, mais aussi la fréquence des éléments en double. Par exemple, si list1 était [“A”, “B”, “A”] et que list2 était [“A”, “B”, “B”], l’approche Set considérerait égales.

Si vous devez être insensible à l’ordre mais sensible à la fréquence des doublons, vous pouvez soit:

  • sortinger les deux listes (ou copies) avant de les comparer, comme dans cette réponse à une autre question
  • ou copier tous les éléments dans un multiset

J’ai posté un tas de choses dans les commentaires, je pense qu’il mérite sa propre réponse.

Comme tout le monde le dit ici, utiliser equals () dépend de la commande. Si vous ne vous souciez pas de la commande, vous avez 3 options.

Option 1

Use containsAll() . Cette option n’est pas idéale, à mon avis, car elle offre des performances optimales, O (n ^ 2).

Option 2

Il y a deux variantes à cela:

2a) Si vous ne tenez pas à maintenir l’ordre de vos listes … utilisez Collections.sort() dans les deux listes. Ensuite, utilisez les equals() . Ceci est O (nlogn), parce que vous faites deux sortes, puis une comparaison O (n).

2b) Si vous devez maintenir l’ordre des listes, vous pouvez d’abord copier les deux listes. Vous pouvez ensuite utiliser la solution 2a sur les deux listes copiées. Cependant, cela pourrait ne pas être intéressant si la copie coûte très cher.

Cela mène à:

Option 3

Si vos exigences sont identiques à celles de la partie 2b , la copie est trop coûteuse. Vous pouvez utiliser un TreeSet pour faire le sorting pour vous. Videz chaque liste dans son propre TreeSet. Il sera sortingé dans l’ensemble et les listes d’origine restront intactes. Effectuez ensuite une comparaison equals() sur les deux TreeSet . Les TreeSets s peuvent être construits en temps O (nlogn), et les equals() sont O (n).

Faites votre choix :-).

EDIT: J’ai presque oublié la même mise en garde que Laurence Gonsalves souligne. L’implémentation de TreeSet éliminera les doublons. Si vous vous souciez des doublons, vous aurez besoin d’une sorte de multiset sortingé.

Si vous utilisez (ou êtes heureux d’utiliser) Apache Commons Collections, vous pouvez utiliser CollectionUtils.isEqualCollection qui “renvoie true si les Collections données ne contiennent exactement les mêmes éléments avec exactement les mêmes cardinalités”.

Je sais que c’est un vieux sujet, mais aucune des autres réponses n’a complètement résolu mon cas d’utilisation (je suppose que Guava Multiset pourrait faire la même chose, mais il n’y a pas d’exemple ici). Veuillez excuser mon formatage. Je suis encore nouveau à poster sur l’échange de stack. En outre laissez-moi savoir s’il y a des erreurs

Disons que vous avez la List a et la List b et que vous voulez vérifier si elles sont égales aux conditions suivantes:

1) O (n) durée de fonctionnement prévue
2) L’égalité est définie comme suit: Pour tous les éléments de a ou b, le nombre de fois que l’élément apparaît dans a est égal au nombre de fois où l’élément apparaît dans b. L’égalité d’élément est définie comme T.equals ()

 private boolean listsAreEquivelent(List< ? extends Object> a, List< ? extends Object> b) { if(a==null) { if(b==null) { //Here 2 null lists are equivelent. You may want to change this. return true; } else { return false; } } if(b==null) { return false; } Map tempMap = new HashMap<>(); for(Object element : a) { Integer currentCount = tempMap.get(element); if(currentCount == null) { tempMap.put(element, 1); } else { tempMap.put(element, currentCount+1); } } for(Object element : b) { Integer currentCount = tempMap.get(element); if(currentCount == null) { return false; } else { tempMap.put(element, currentCount-1); } } for(Integer count : tempMap.values()) { if(count != 0) { return false; } } return true; } 

Le temps d’exécution est O (n) car nous effectuons des insertions O (2 * n) dans un hashmap et des sélections de hashmap O (3 * n). Je n’ai pas entièrement testé ce code, alors méfiez-vous 🙂

 //Returns true: listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","A")); listsAreEquivelent(null,null); //Returns false: listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","B")); listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("A","B")); listsAreEquivelent(Arrays.asList("A","A","B"),null); 

Essayez cette version qui ne nécessite pas d’ordre pour être la même mais supporte le multiple de la même valeur. Ils ne correspondent que si chacun a la même quantité de valeur.

 public boolean arraysMatch(List elements1, List elements2) { // Optional quick test since size must match if (elements1.size() != elements2.size()) { return false; } List work = newArrayList(elements2); for (Ssortingng element : elements1) { if (!work.remove(element)) { return false; } } return work.isEmpty(); } 

Très tard à la fête, mais je voulais append cette vérification de sécurité nulle:

 Objects.equals(list1, list2) 

Solution pour le cas où deux listes ont les mêmes éléments, mais un ordre différent:

 public boolean isDifferentLists(List listOne, List listTwo) { if(isNullLists(listOne, listTwo)) { return false; } if (hasDifferentSize(listOne, listTwo)) { return true; } List listOneCopy = Lists.newArrayList(listOne); List listTwoCopy = Lists.newArrayList(listTwo); listOneCopy.removeAll(listTwoCopy); return CollectionUtils.isNotEmpty(listOneCopy); } private boolean isNullLists(List listOne, List listTwo) { return listOne == null && listTwo == null; } private boolean hasDifferentSize(List listOne, List listTwo) { return (listOne == null && listTwo != null) || (listOne != null && listTwo == null) || (listOne.size() != listTwo.size()); } 

La réponse de Tom est excellente. Je suis entièrement d’accord avec ses réponses!

Un aspect intéressant de cette question est de savoir si vous avez besoin du type List lui-même et de son ordre inhérent.

Si ce n’est pas le cas, vous pouvez réduire à Iterable ou Collection ce qui vous donne une certaine flexibilité en matière de transmission des structures de données sortingées au moment de l’insertion, plutôt qu’au moment où vous souhaitez vérifier.

Si l’ordre ne compte jamais (et que vous n’avez pas d’éléments en double), envisagez d’utiliser un Set .

Si l’ordre est important mais qu’il est défini par le temps d’insertion (et que vous n’avez pas de doublons), considérez un LinkedHashSet qui est comme un TreeSet mais qui est ordonné par temps d’insertion (les doublons ne sont pas comptabilisés). Cela vous donne également O(1) access amorti insted de O(log n) .

La méthode d’égalité sur List le fera, les listes seront classées, donc pour être égales deux listes doivent avoir les mêmes éléments dans le même ordre.

 return list1.equals(list2); 
 list1.equals(list2); 

Si votre liste contient une classe MyClass personnalisée, cette classe doit remplacer la fonction equals .

  class MyClass { int field=0; @0verride public boolean equals(Object other) { if(this==other) return true; if(other==null || !(other instanceof MyClass)) return false; return this.field== MyClass.class.cast(other); } } 

Remarque: si vous souhaitez tester égal à java.util.Set plutôt qu’à java.util.List , votre object doit alors remplacer la fonction hashCode .

Exemple de code:

 public static '< 'T'>' boolean isListDifferent(List'< 'T'>' previousList, List'< 'T'>' newList) { int sizePrevoisList = -1; int sizeNewList = -1; if (previousList != null && !previousList.isEmpty()) { sizePrevoisList = previousList.size(); } if (newList != null && !newList.isEmpty()) { sizeNewList = newList.size(); } if ((sizePrevoisList == -1) && (sizeNewList == -1)) { return false; } if (sizeNewList != sizePrevoisList) { return true; } List n_prevois = new ArrayList(previousList); List n_new = new ArrayList(newList); try { Collections.sort(n_prevois); Collections.sort(n_new); } catch (ClassCastException exp) { return true; } for (int i = 0; i < sizeNewList; i++) { Object obj_prevois = n_prevois.get(i); Object obj_new = n_new.get(i); if (obj_new.equals(obj_prevois)) { // Object are same } else { return true; } } return false; } 

En plus de la réponse de Laurence, si vous souhaitez également le rendre null-safe:

 private static  boolean listEqualsIgnoreOrder(List list1, List list2) { if (list1 == null) return list2==null; if (list2 == null) return list1 == null; return new HashSet<>(list1).equals(new HashSet<>(list2)); } 

Vous pouvez utiliser la bibliothèque org.apache.commons.collections d’Apache: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html

 public static boolean isEqualList(java.util.Collection list1, java.util.Collection list2) 

Vérifiez que les deux listes ne sont pas nulles. Si leurs tailles sont différentes, ces listes ne sont pas égales. Construisez des cartes composées des éléments des listes sous forme de clés et de leurs répétitions en tant que valeurs et comparez les cartes.

Hypothèses, si les deux listes sont nulles, je les considère égales.

 private boolean compareLists(List< ?> l1, List< ?> l2) { if (l1 == null && l2 == null) { return true; } else if (l1 == null || l2 == null) { return false; } if (l1.size() != l2.size()) { return false; } Map< ?, Integer> m1 = toMap(l1); Map< ?, Integer> m2 = toMap(l2); return m1.equals(m2); } private Map toMap(List< ?> list) { //Effective size, not to resize in the future. int mapSize = (int) (list.size() / 0.75 + 1); Map map = new HashMap<>(mapSize); for (Object o : list) { Integer count = map.get(o); if (count == null) { map.put(o, 1); } else { map.put(o, ++count); } } System.out.println(map); return map; } 

Veuillez noter que la méthode doit être définie correctement pour ces objects. https://stackoverflow.com/a/24814634/4587961

Cela dépend de la classe concrète que vous utilisez. La classe abstraite AbstractCollection a une méthode appelée containsAll (Collection) qui prend une autre collection (une liste est une collection) et:

Renvoie true si cette collection contient tous les éléments de la collection spécifiée.

Donc, si une ArrayList est passée, vous pouvez appeler cette méthode pour voir si elles sont exactement identiques.

  List foo = new ArrayList(); List bar = new ArrayList(); Ssortingng str = "foobar"; foo.add(str); bar.add(str); foo.containsAll(bar); 

La raison de la présence de containsAll () est qu’elle parcourt la première liste en recherchant la correspondance dans la deuxième liste. Donc, s’ils ne sont pas dans l’ordre, est égal à () et ne les reprendra pas.

EDIT: Je veux juste faire un commentaire ici sur le temps de fonctionnement amorti des différentes options offertes. Le temps d’exécution est-il important? Sûr. Est-ce la seule chose à considérer? Non.

Le coût de la copie de CHAQUE élément unique de vos listes dans d’autres listes prend du temps, et prend également une bonne partie de la mémoire (doublant efficacement la mémoire que vous utilisez).

Donc, si la mémoire de votre JVM n’est pas un problème (ce qui devrait être généralement le cas), vous devez quand même prendre en compte le temps nécessaire pour copier chaque élément de deux listes dans deux TreeSets. Rappelez-vous qu’il sortinge chaque élément lorsqu’il y pénètre.

Mon dernier conseil? Vous devez tenir compte de votre dataset et du nombre d’éléments que vous avez dans votre jeu de données, ainsi que de la taille de chaque object dans votre dataset avant de pouvoir prendre une bonne décision ici. Jouez avec eux, créez-en un dans chaque sens et voyez ceux qui courent plus vite. C’est un bon exercice.