Einfacher Weg, um herauszufinden, ob zwei verschiedene Listen genau die gleichen Elemente enthalten?

252

Was ist der einfachste Weg, um festzustellen, ob zwei Listen in den Standard-Java-Bibliotheken genau dieselben Elemente enthalten?

Es sollte keine Rolle spielen, ob die beiden Listen dieselbe Instanz sind oder nicht, und es sollte keine Rolle spielen, ob die Typparameter der Listen unterschiedlich sind.

z.B

List list1
List<String> list2; 
// ... construct etc

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

Wahrscheinlich starrt mich etwas ins Gesicht, das ich kenne :-)


EDIT: Zur Verdeutlichung habe ich nach genau den gleichen Elementen und der gleichen Anzahl von Elementen gesucht.

Grundlefleck
quelle
Müssen die Elemente in derselben Reihenfolge sein?
Michael Myers
Dies hat möglicherweise keine Auswirkungen auf Sie, aber achten Sie darauf, dass persistente Sets im Ruhezustand manchmal nicht den
gleichen

Antworten:

366

Wenn Sie sich für Ordnung interessieren, verwenden Sie einfach die Methode equals:

list1.equals(list2)

Aus dem Javadoc:

Vergleicht das angegebene Objekt mit dieser Liste auf Gleichheit. Gibt nur dann true zurück, wenn das angegebene Objekt auch eine Liste ist, beide Listen dieselbe Größe haben und alle entsprechenden Elementpaare in den beiden Listen gleich sind. (Zwei Elemente e1 und e2 sind gleich, wenn (e1 == null? E2 == null: e1.equals (e2)).) Mit anderen Worten, zwei Listen werden als gleich definiert, wenn sie dieselben Elemente in derselben Reihenfolge enthalten . Diese Definition stellt sicher, dass die Methode equals in verschiedenen Implementierungen der List-Schnittstelle ordnungsgemäß funktioniert.

Wenn Sie unabhängig von der Reihenfolge prüfen möchten, können Sie alle Elemente in Sets kopieren und für die resultierenden Sets Gleichheit verwenden:

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

Eine Einschränkung dieses Ansatzes besteht darin, dass nicht nur die Reihenfolge, sondern auch die Häufigkeit doppelter Elemente ignoriert wird. Wenn beispielsweise list1["A", "B", "A"] und list2["A", "B", "B"] Setwäre, würde der Ansatz sie als gleich betrachten.

Wenn Sie unempfindlich gegenüber Bestellungen sein müssen, aber empfindlich gegenüber der Häufigkeit von Duplikaten, können Sie entweder:

Laurence Gonsalves
quelle
54
Könnten Sie nicht includesAll verwenden, wenn Sie unabhängig von der Reihenfolge prüfen möchten?
Laz
6
Ich weiß nichts über die Implementierungsdetails von includesAll, aber es scheint, als könnte es schlecht sein. Wenn enthältAlle Aufrufe enthält immer wieder (), haben Sie eine O (n ^ 2) -Alge. Die Sätze insgesamt sollten O (nlogn)
Tom
6
Wenn die Mengen nur O (nlogn) sein sollen, besteht ein anderer Ansatz darin, Collections.sort () in einer Liste aufzurufen und dann equals zu verwenden. Wenn Sie jedoch die Ordnung erhalten möchten, müssen Sie die Liste kopieren. Dies kann teuer sein und die festgelegte Lösung begünstigen. Sie müssen also über Ihre Situation nachdenken :-).
Tom
1
@amischiefr: Schlagen Sie vor, dass O (n ^ 2) das Beste ist, was Sie tun können?
Tom
8
@Dennis Die Größenprüfung funktioniert wirklich nur, wenn Sie wissen, dass jede Liste nur unterschiedliche Elemente enthält. Zum Beispiel sind gegeben a = [x, y, x]und b = [x, y, z]dann die Größen gleich und b.containsAll(a)geben true zurück, enthalten aber bein Element, das nicht in ist a.
Laurence Gonsalves
95

Ich habe ein paar Dinge in Kommentaren gepostet, von denen ich denke, dass sie eine eigene Antwort rechtfertigen.

Wie jeder hier sagt, hängt die Verwendung von equals () von der Reihenfolge ab. Wenn Sie sich nicht für die Bestellung interessieren, haben Sie 3 Möglichkeiten.

Option 1

Verwenden Sie containsAll(). Diese Option ist meiner Meinung nach nicht ideal, da sie die Worst-Case-Leistung O (n ^ 2) bietet.

Option 2

Hierfür gibt es zwei Variationen:

2a) Wenn Sie die Reihenfolge Ihrer Listen nicht beibehalten möchten, verwenden Sie sie Collections.sort()für beide Listen. Dann benutzen Sie dieequals() . Dies ist O (nlogn), weil Sie zwei Sortierungen und dann einen O (n) -Vergleich durchführen.

2b) Wenn Sie die Reihenfolge der Listen beibehalten müssen, können Sie beide Listen zuerst kopieren. DANN können Sie Lösung 2a verwenden für beide kopierten Listen verwenden. Dies kann jedoch unattraktiv sein, wenn das Kopieren sehr teuer ist.

Dies führt zu:

Option 3

Wenn Ihre Anforderungen mit denen von Teil 2b übereinstimmen , das Kopieren jedoch zu teuer ist. Sie können ein TreeSet verwenden, um die Sortierung für Sie durchzuführen. Speichern Sie jede Liste in einem eigenen TreeSet. Es wird im Set sortiert und die ursprünglichen Listen bleiben erhalten. Führen Sie dann einen equals()Vergleich für beide TreeSets durch. Das TreeSetss kann in O (nlogn) -Zeit erstellt werden, und das equals()ist O (n).

Treffen Sie Ihre Wahl :-).

EDIT: Ich habe fast die gleiche Einschränkung vergessen, auf die Laurence Gonsalves hinweist. Die TreeSet-Implementierung eliminiert Duplikate. Wenn Sie sich für Duplikate interessieren, benötigen Sie eine Art sortiertes Multiset.

Tom
quelle
Wenn Sie sich für Duplikate interessieren, können Sie vor allen anderen Tests jederzeit testen, ob die Größe der Sammlungen gleich ist.
Laz
Wenn Duplikate auf Ungleichheit hinweisen, muss die Größe der Listen gleich sein, bevor eine Gleichheitsprüfung erfolgreich sein kann.
Laz
7
@laz: Das Überprüfen der Größe funktioniert nicht, wenn verschiedene Elemente in den beiden Listen dupliziert werden. Beispiel: [A, A, B] und [A, B, B] sind gleich groß.
Laurence Gonsalves
@Laurence: Ich stimme zu, dass der Beitrag von Laz etwas verwirrend ist (ich habe ihn einige Male gelesen, bevor ich ihn verstanden habe). Ich gehe davon aus, dass er nur versucht, eine "Verknüpfung" für den Sonderfall bereitzustellen, wenn zwei Bedingungen gelten: (1) Duplikate sind wichtig, und (2) die Listengrößen sind unterschiedlich. In Ihrem Beispiel denke ich, dass Laz immer noch sagt, dass es notwendig ist, dieselben Überprüfungen durchzuführen, die wir besprochen haben. (Zumindest habe ich es so gelesen). Wenn Duplikate keine Rolle spielen, können Sie die Größe nicht als Sonderfallprüfung verwenden. Aber wenn die 2 Bedingungen gelten, können Sie einfach sagen "if (list1.size ()! = List2.size ()) return false;
Tom
9
ContainsAll würde ich denke, geben Sie die falsche Antwort, Sie müsstenAll in beide Richtungen enthalten. a.containsAll(b) && b.containsAll(a)
Richard Tingle
24

Wenn Sie Apache Commons-Sammlungen verwenden (oder gerne verwenden), können Sie CollectionUtils.isEqualCollection verwenden, die "true zurückgibt, wenn die angegebenen Sammlungen genau dieselben Elemente mit genau denselben Kardinalitäten enthalten".

Daiscog
quelle
Sehr schöne Hashmap-basierte Implementierung. Die Laufzeit sollte O (n) sein, und wenn es viele sich wiederholende Elemente gibt, wird nur minimaler Speicher verwendet, um den Überblick zu behalten (verfolgt im Grunde die Häufigkeit (Kardinalität) von Elementen mithilfe einer Karte für jede Sammlung). Nachteil ist, dass es eine zusätzliche O (n) -Speicherauslastung hat.
Muhd
17

Sehr spät zur Party, wollte aber diesen Null-Safe-Check hinzufügen:

Objects.equals(list1, list2)
Reimeus
quelle
8

Ich weiß, dass dies ein alter Thread ist, aber keine der anderen Antworten hat meinen Anwendungsfall vollständig gelöst (ich denke, Guava Multiset könnte dasselbe tun, aber hier gibt es kein Beispiel). Bitte entschuldigen Sie meine Formatierung. Ich bin noch neu im Stack Exchange. Lassen Sie mich außerdem wissen, wenn Fehler vorliegen

Nehmen wir an, Sie haben List<T>a und List<T>b und möchten überprüfen, ob sie den folgenden Bedingungen entsprechen:

1) O (n) erwartete Laufzeit
2) Gleichheit ist definiert als: Für alle Elemente in a oder b ist die Häufigkeit, mit der das Element in a auftritt, gleich der Häufigkeit, mit der das Element in b auftritt. Elementgleichheit ist definiert als 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;
}

Die Laufzeit beträgt O (n), da O (2 * n) in eine Hashmap eingefügt und O (3 * n) ausgewählt wird. Ich habe diesen Code nicht vollständig getestet, also Vorsicht :)

//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);
Andrew
quelle
5

Probieren Sie diese Version aus, für die keine gleiche Reihenfolge erforderlich ist, die jedoch mehrere gleiche Werte unterstützt. Sie stimmen nur überein, wenn jede die gleiche Menge eines Wertes hat.

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();
}
Lee Meador
quelle
work.remove (Element) ist O (n), also ist diese Lösung O (n ^ 2)
Andrew
Oder O (n1 * n2), was ähnlich ist
Lee Meador
Ich habe auch die gleiche Strategie angewendet, weil sie alle Szenarien behandelt und die Sammlungsgröße nicht so groß ist, dann spielt O (n ^ 2) keine Rolle
Naresh Joshi
3

Die Methode equals in List führt dies aus. Listen werden geordnet. Um gleich zu sein, müssen zwei Listen dieselben Elemente in derselben Reihenfolge haben.

return list1.equals(list2);
Daveb
quelle
3
Listen werden nur bestellt, wenn Sie sie sortieren.
Michael Myers
Seufz @ mich. Eine so offensichtliche Antwort. Sie wissen, dass es ein zu langer Tag war, an dem Sie nicht einmal mehr eine Webseite mit Strg + F drücken können. :)
Grundlefleck
2
@mmyers: Artikel in Listen werden nur bestellt, wenn Sie sie sortieren. Listen selbst haben eine implizite Reihenfolge der Elemente (nach Index), die sich nur ändern, wenn Sie die Elemente in der Liste ändern. (vs. Sets oder Sammlungen, bei denen keine Garantie für eine konsistente Reihenfolge besteht, wenn Sie sie zweimal durchlaufen)
Jason S
Ich denke, daveb bedeutet, dass Listen geordnet sind, dass List.equals die Reihenfolge der Elemente berücksichtigt, um die Gleichheit zu bestimmen. Siehe den Javadoc.
laz
2
Was ich meine ist, dass eine Liste mit {"A", "B"} und eine Liste mit {"B", "A"} mit dieser Methode ungleich wäre. Das mag durchaus beabsichtigt sein, aber ich wollte sicherstellen, dass niemand es übersieht.
Michael Myers
3

Lösung für den Fall, dass zwei Listen dieselben Elemente, aber unterschiedliche Reihenfolge haben:

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());
}
Pavlo Zvarych
quelle
2
Ich denke, Sie müssen listTwo nicht kopieren.
AjahnCharles
1
Vielleicht möchten Sie auch wissen , warum Sie removeAll()anstelle von verwendet haben containsAll()(nach meinem Verständnis würde der Ansatz includesAll () die Listen fälschlicherweise als gleich melden, wenn listTwo Duplikate enthält, die nur einmal in listOne enthalten sind).
AjahnCharles
3

Toms Antwort ist ausgezeichnet. Ich stimme seinen Antworten voll und ganz zu!

Ein interessanter Aspekt dieser Frage ist, ob Sie die brauchen List Typ selbst und seine inhärente Reihenfolge .

Wenn nicht, können Sie Datenstrukturen, die nach der Einfügezeit sortiert sind, und nicht zu dem Zeitpunkt, zu dem Sie sie überprüfen möchten, verschlechtern Iterableoder Collectionflexibel weitergeben.

Wenn die Reihenfolge keine Rolle spielt (und Sie keine doppelten Elemente haben), sollten Sie a verwenden Set.

Wenn die Reihenfolge wichtig ist, aber durch LinkedHashSetdie Einfügezeit definiert ist (und Sie keine Duplikate haben), berücksichtigen Sie eine, die einem TreeSet ähnelt, aber nach der Einfügezeit sortiert ist (Duplikate werden nicht gezählt). Dies gibt Ihnen auch einen O(1)amortisierten Zugriff O(log n).

Alex
quelle
2

Beispielcode:

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;
}
Jaydip Halake
quelle
2

Zusätzlich zu Laurences Antwort, wenn Sie es auch null-sicher machen möchten:

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));
}
Felixuko
quelle
1
Sie können die Überprüfungen vereinfachen:if (list1 == null) return list2==null; if (list2 == null) return false;
Xerus
Funktioniert nicht, wenn die Listen [a, a, b, c] und [a, b, c] sind, und gibt true zurück, es sei denn, Sie fügen eine zusätzliche Prüfung hinzu, um sicherzustellen, dass die Größe der Listen gleich ist.
Venkat Madhav
2
list1.equals(list2);

Wenn Ihre Liste eine benutzerdefinierte Klasse MyClass enthält, muss diese Klasse die equalsFunktion überschreiben .

 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;
        }
  }

Hinweis: Wenn Sie Equals auf einer java.util.Set anstelle von a testen möchten, java.util.Listmuss Ihr Objekt die hashCode Funktion überschreiben .

Pierre
quelle
1
sollte die Zeile: return this.field == MyClass.class.cast (other); be return this.field == MyClass.class.cast (other) .field;
Alpere
@alpere oh! Du hast recht ! Ich werde es reparieren. Vielen Dank !
Pierre
0

Sie können die Bibliothek org.apache.commons.collections von Apache verwenden: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html

public static boolean isEqualList(java.util.Collection list1,
                              java.util.Collection list2)
David Zhao
quelle
Dies erfordert auch, dass Listenelemente in derselben Reihenfolge vorliegen.
Josh-Cain
Sie können die Liste vor dem Vergleich sortieren
David Zhao
Natürlich können Sie dies tun, vorausgesetzt, die Typen sind in der Liste gespeichert oder sortierbar (oder Sie haben einen Komparator eingerichtet). Der Apache-Implementierungsalgorithmus unterscheidet sich jedoch nicht von den regulären list1.equals (list2), außer dass er statisch ist. Ich sehe, wo ich die Frage falsch verstanden habe, und es wurde tatsächlich gefragt, wie Listenelemente in derselben Reihenfolge verglichen werden sollen. Mein Fehler!
Josh-Cain
@ DavidZhao: Link ist tot.
Aniket Kulkarni
0

Überprüfen Sie, ob beide Listen keine Nullen sind. Wenn ihre Größen unterschiedlich sind, sind diese Listen nicht gleich. Erstellen Sie Karten, die aus den Elementen der Listen als Schlüssel und deren Wiederholungen als Werte bestehen, und vergleichen Sie die Karten.

Annahmen, wenn beide Listen Nullen sind, halte ich sie für gleich.

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;
}

Bitte beachten Sie, dass für diese Objekte die Methode equals richtig definiert werden sollte. https://stackoverflow.com/a/24814634/4587961

Yan Khonski
quelle
1
Sie haben angenommen, dass ein Element nicht in jeder Liste unterschiedlich oft vorhanden sein kann, z. B. [x, x, y]vs [x, y, y]würde bei Ihrer Implementierung true zurückgeben.
AjahnCharles
@ CodeConfident, vielen Dank! Ich habe die Antwort aktualisiert. Ich werde ein Mao benutzen!
Yan Khonski
-2

Dies hängt davon ab, welche konkrete List-Klasse Sie verwenden. Die abstrakte Klasse AbstractCollection verfügt über eine Methode namens includesAll (Collection), die eine andere Sammlung (eine Liste ist eine Sammlung) verwendet, und:

Gibt true zurück, wenn diese Auflistung alle Elemente in der angegebenen Auflistung enthält.

Wenn also eine ArrayList übergeben wird, können Sie diese Methode aufrufen, um festzustellen, ob sie genau gleich sind.

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

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

    foo.containsAll(bar);

Der Grund für includesAll () ist, dass die erste Liste durchlaufen wird, um nach der Übereinstimmung in der zweiten Liste zu suchen. Wenn sie also nicht in Ordnung sind, wird equals () sie nicht abholen.

BEARBEITEN: Ich möchte hier nur einen Kommentar zur amortisierten Laufzeit der Ausführung der verschiedenen angebotenen Optionen abgeben. Ist die Laufzeit wichtig? Sicher. Ist es das einzige, was Sie berücksichtigen sollten? Nein.

Die Kosten für das Kopieren JEDES einzelnen Elements aus Ihren Listen in andere Listen nehmen Zeit in Anspruch und beanspruchen außerdem einen guten Speicherplatz (wodurch der von Ihnen verwendete Speicher effektiv verdoppelt wird).

Wenn der Speicher in Ihrer JVM kein Problem darstellt (was im Allgemeinen der Fall sein sollte), müssen Sie dennoch die Zeit berücksichtigen, die erforderlich ist, um jedes Element aus zwei Listen in zwei TreeSets zu kopieren. Denken Sie daran, dass jedes Element beim Eintritt sortiert wird.

Mein letzter Rat? Sie müssen Ihren Datensatz und die Anzahl der Elemente in Ihrem Datensatz sowie die Größe jedes Objekts in Ihrem Datensatz berücksichtigen, bevor Sie hier eine gute Entscheidung treffen können. Spielen Sie mit ihnen herum, erstellen Sie eine in jede Richtung und sehen Sie, welche schneller läuft. Es ist eine gute Übung.

amischiefr
quelle
2
Müsste es nicht foo.containsAll (bar) && bar.containsAll (foo) sein; ?
Carl Manaster
Nein, es geht durch jedes Element in foo und prüft, ob der Balken dieses Element enthält. Anschließend wird sichergestellt, dass die Länge der beiden Listen gleich ist. Wenn es für jedes foo ein Element in bar gibt, so dass foo.element == bar.element und foo.length == bar.length, dann enthalten sie dieselben Elemente.
Amischiefr
Wissen wir, ob es eine Effizienzgarantie gibt? oder ist das typisch O (n ^ 2)?
Tom
Wie bei jedem anderen Array, das nach einem passenden Element sucht, beträgt die Laufzeit im ungünstigsten Fall O (n ^ 2). In diesem Fall sieht es so aus, als würde die Implementierung tatsächlich jeweils ein Element durchlaufen, um nach der Übereinstimmung zu suchen. Ich werde nicht über die amortisierte Laufzeit spekulieren, aber ja, der schlimmste Fall ist O (n ^ 2).
Amischiefr
1
Dies funktioniert nicht: {1,2,2} .containsAll ({1,1,2}) und umgekehrt, und die beiden Listen haben dieselbe Größe.
Comco