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 trouver si deux listes contiennent exactement les mêmes éléments dans les bibliothèques Java standard?

Peu importe que les deux listes soient la même instance ou non, et peu importe si le paramètre de type des listes est différent.

par exemple

List list1
List<String> 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 nombre d'éléments, dans l'ordre.

Si vous vous souciez de la commande, utilisez simplement la méthode equals:

list1.equals(list2)

Du javadoc:

Compare l'objet spécifié avec cette liste pour l'égalité. Renvoie true si et seulement si l'objet spécifié est également une liste, les deux listes ont la même taille et toutes les paires d'éléments correspondantes dans les 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 pour être é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 les ensembles et utiliser des égaux sur les ensembles résultants:

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

Une limitation de cette approche est qu'elle ignore non seulement l'ordre, mais également la fréquence des éléments en double. Par exemple, si list1était ["A", "B", "A"] et list2était ["A", "B", "B"], l' Setapproche les considérerait comme égaux.

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

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

J'ai posté un tas de choses dans les commentaires, je pense que cela mérite sa propre réponse.

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

Option 1

Utilisez containsAll(). Cette option n'est pas idéale, à mon avis, car elle offre les pires performances, O (n ^ 2).

Option 2

Il existe deux variantes:

2a) Si vous ne vous souciez pas de maintenir l'ordre de vos listes ... utilisez-les Collections.sort()sur les deux listes. Utilisez ensuite le equals(). Il s'agit de O (nlogn), car vous effectuez deux sortes, puis une comparaison O (n).

2b) Si vous devez maintenir l'ordre des listes, vous pouvez d'abord copier les deux listes. ALORS vous pouvez utiliser la solution 2a sur les deux listes copiées. Cependant, cela peut ne pas être attrayant si la copie est très coûteuse.

Cela mène à:

Option 3

Si vos exigences sont les mêmes que celles de la partie 2b , mais la copie est trop chère. Vous pouvez utiliser un TreeSet pour faire le tri pour vous. Videz chaque liste dans son propre TreeSet. Il sera trié dans l'ensemble et les listes originales resteront intactes. Effectuez ensuite une equals()comparaison sur les deux TreeSetart. Le TreeSetss peut être construit en temps O (nlogn), et le equals()est O (n).

Faites votre choix :-).

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

Si vous utilisez (ou êtes heureux d'utiliser) des collections Apache Commons, vous pouvez utiliser CollectionUtils.isEqualCollection qui "renvoie vrai si les collections données contiennent exactement les mêmes éléments avec exactement les mêmes cardinalités."

Très tard pour la fête mais je voulais ajouter ce contrôle de sécurité nul:

Objects.equals(list1, list2)

Je sais que c'est un vieux fil, 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 ma mise en forme. Je suis encore nouveau pour poster sur l'échange de pile. De plus, faites-moi savoir s'il y a des erreurs

Disons que vous avez List<T>a et List<T>b et que vous voulez vérifier s'ils sont égaux aux conditions suivantes:

1) O (n) durée de fonctionnement attendue
2) L'égalité est définie comme: Pour tous les éléments dans a ou b, le nombre de fois où l'élément apparaît dans a est égal au nombre de fois où l'élément apparaît dans b. L'égalité des éléments est définie par 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<Object, Integer> 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 une table de hachage et des sélections de table de hachage O (3 * n). Je n'ai pas entièrement testé ce code, alors attention :)

//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 que l'ordre soit le même, mais qui prend en charge plusieurs de la même valeur. Ils ne correspondent que si chacun a la même quantité de n'importe quelle valeur.

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

La méthode equals sur List fera cela, les listes sont ordonnées, donc pour être égales, deux listes doivent avoir les mêmes éléments dans le même ordre.

return list1.equals(list2);

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

public boolean isDifferentLists(List<Integer> listOne, List<Integer> listTwo) {
    if(isNullLists(listOne, listTwo)) {
        return false;
    }

    if (hasDifferentSize(listOne, listTwo)) {
        return true;
    }

    List<Integer> listOneCopy = Lists.newArrayList(listOne);
    List<Integer> listTwoCopy = Lists.newArrayList(listTwo);
    listOneCopy.removeAll(listTwoCopy);

    return CollectionUtils.isNotEmpty(listOneCopy);
}

private boolean isNullLists(List<Integer> listOne, List<Integer> listTwo) {
    return listOne == null && listTwo == null;
}

private boolean hasDifferentSize(List<Integer> listOne, List<Integer> 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 Listtype lui-même et de son ordre inhérent.

Sinon, vous pouvez dégrader en Iterableou Collectionce qui vous donne une certaine flexibilité pour passer autour des structures de données qui sont triées au moment de l'insertion, plutôt qu'au moment où vous voulez vérifier.

Si la commande n'a jamais d'importance (et que vous n'avez pas d'éléments en double), envisagez d'utiliser a Set.

Si l'ordre importe mais est défini par le temps d'insertion (et que vous n'avez pas de doublons), considérez un LinkedHashSetqui est comme un TreeSet mais est ordonné par le temps d'insertion (les doublons ne sont pas comptés). Cela vous donne également un O(1)accès amorti instantanément O(log n).

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 la rendre null-safe:

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

list1.equals(list2);

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

 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).field;
        }
  }

Remarque: si vous souhaitez tester égal sur un java.util.Set plutôt que sur un java.util.List, votre objet doit remplacer la hashCode fonction.

List.equals ()

http://java.sun.com/j2se/1.5/docs/api/java/util/List.html#equals(java.lang.Object)

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. Créez des cartes composées des éléments des listes sous forme de clés et de leurs répétitions sous forme de 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<Object, Integer> toMap(List<?> list) {
    //Effective size, not to resize in the future.
    int mapSize = (int) (list.size() / 0.75 + 1);
    Map<Object, Integer> 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 les méthodes égales doivent être correctement définies pour ces objets. https://stackoverflow.com/a/24814634/4587961

Cela dépend de la classe List concrète que vous utilisez. La classe abstraite AbstractCollection a une méthode appelée containsAll (Collection) qui prend une autre collection (une List 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 les mêmes.

       List foo = new ArrayList();
    List bar = new ArrayList();
    String str = "foobar";

    foo.add(str);
    bar.add(str);

    foo.containsAll(bar);

La raison de containsAll () est qu'il parcourt la première liste à la recherche de la correspondance dans la deuxième liste. Donc, s'ils sont en panne, equals () ne le ramassera pas.

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

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

Donc, si la mémoire de votre machine virtuelle Java n'est pas un problème (ce qu'elle devrait généralement être), vous devez toujours prendre en compte le temps qu'il faut pour copier chaque élément de deux listes dans deux TreeSets. N'oubliez pas qu'il trie chaque élément au fur et à mesure qu'il y entre.

Mon dernier conseil? Vous devez prendre en compte votre ensemble de données et le nombre d'éléments que vous avez dans votre ensemble de données, ainsi que la taille de chaque objet de votre ensemble de données avant de pouvoir prendre une bonne décision ici. Jouez avec eux, créez-en un dans chaque sens et voyez lequel tourne le plus vite. C'est un bon exercice.