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.
java
collections
Grundlefleck
quelle
quelle
Antworten:
Wenn Sie sich für Ordnung interessieren, verwenden Sie einfach die Methode equals:
Aus dem Javadoc:
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:
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"] undlist2
["A", "B", "B"]Set
wä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:
quelle
a = [x, y, x]
undb = [x, y, z]
dann die Größen gleich undb.containsAll(a)
geben true zurück, enthalten aberb
ein Element, das nicht in ista
.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 beideTreeSet
s durch. DasTreeSets
s kann in O (nlogn) -Zeit erstellt werden, und dasequals()
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.
quelle
a.containsAll(b) && b.containsAll(a)
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".
quelle
Sehr spät zur Party, wollte aber diesen Null-Safe-Check hinzufügen:
quelle
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 undList<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 ()
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 :)
quelle
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.
quelle
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.
quelle
Lösung für den Fall, dass zwei Listen dieselben Elemente, aber unterschiedliche Reihenfolge haben:
quelle
removeAll()
anstelle von verwendet habencontainsAll()
(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).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
Iterable
oderCollection
flexibel 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
LinkedHashSet
die 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 einenO(1)
amortisierten ZugriffO(log n)
.quelle
Beispielcode:
quelle
Zusätzlich zu Laurences Antwort, wenn Sie es auch null-sicher machen möchten:
quelle
if (list1 == null) return list2==null; if (list2 == null) return false;
Wenn Ihre Liste eine benutzerdefinierte Klasse MyClass enthält, muss diese Klasse die
equals
Funktion überschreiben .Hinweis: Wenn Sie Equals auf einer java.util.Set anstelle von a testen möchten,
java.util.List
muss Ihr Objekt diehashCode
Funktion überschreiben .quelle
List.equals ()
http://java.sun.com/j2se/1.5/docs/api/java/util/List.html#equals(java.lang.Object)
quelle
Sie können die Bibliothek org.apache.commons.collections von Apache verwenden: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html
quelle
Ü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.
Bitte beachten Sie, dass für diese Objekte die Methode equals richtig definiert werden sollte. https://stackoverflow.com/a/24814634/4587961
quelle
[x, x, y]
vs[x, y, y]
würde bei Ihrer Implementierung true zurückgeben.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:
Wenn also eine ArrayList übergeben wird, können Sie diese Methode aufrufen, um festzustellen, ob sie genau gleich sind.
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.
quelle