Listen vergleichen — Es hört sich immer einfach an, aber die Komplexität steigt mit der Menge an Daten und somit auch der Zeitaufwand.
Eigentlich ist es ganz einfach, man iteriert eine Liste durch und entfernt z. B. aus der zweiten Liste alle Einträge, welche auch in der ersten sind. War das immer möglich und ist am Ende nichts mehr in der zweiten Liste enthalten, dann ist die Liste wohl gleich. (bei Listen mit unique Inhalten)
Dabei stößt man als ersten immer auf das Problem dass man in einer foreach nicht mehr List.Remove(item) nutzen kann, da man diese Liste ja gerade durchiteriert 😉 Work-arround hier: eine For-Schleife, aber rückwärts und dann List.RemoveAt(int i) zu nutzen.
Im Project Medlan wurde dieses Problem bereits Anfang 2012 durch gesprochen und er hatte sogar den gleichen Lösungsansatz mit dem Entfernen der Listeneinträge 🙂
Kurzum, es gibt eine Lösung für das Problem: Seit .NET 3.5 gibt es eine LINQ-Funktion zum Bilder der Schnittmenge A∩B und der Restmenge A\B (Differenz und Komplement).
Alles was man dann nur implementieren sollte ist eine Equals und eine GetHashCode-Funktion um eindeutige Ergebnisse zu erlangen.
Und mit 2 Vergleichen kann man schnell herausfinden, ob die Listen gleich sind:
var diff1 = liste1.Except(liste2).ToList().Count == 0; var diff2 = liste2.Except(liste1).ToList().Count == 0; bool gleichheit = diff1 && diff2;
Update: hier hatte sich der Fehlerteufel eingeschlichen. Richtig muss die Prüfung auf 0 statt, auf liste1.Count sein. Der Vergleich lautet ja “Liste1 außer den Elementen in Liste2” bzw. umgekehrt. Also die Schnittmenge die in 1 enthalten ist, aber nicht in 2. Wenn Gleichheit bestehen soll, darf nirgends mehr drin sein.
Medlan hat bei seinen Tests auch fest gestellt, dass die LINQ-Funktion wesentlich schneller arbeitet, als der 1. Versuch mit dem Entfernen der Elemente.
“Lassen wir den Worten doch Zahlen folgen: Für die 200.000 Einträge benötigen wir gerade mal 200 ms um die Differenzliste zu erstellen. Gut. Man muss fairerweise dazusagen: Man braucht noch die zweite Differenz in die andere Richtung. Aber selbst dann ist der Spuk in ca. 250 ms vorbei.
Und wie sieht das bei 2.500.000 Elementen aus? Was soll ich sagen – die Initialisierung der Elemente dauert länger als der Vergleich (1,5 Sekunden).” (medlan blog)
Am besten den Beitrag auf http://www.project-medlan.de/?p=533 mal lesen 🙂
Hier werden die beiden Methoden nochmal sehr anschaulich dargestellt:
Hallo,
bin gerade zufällig über deinen Beitrag gestolpert. Gefällt mir sehr gut.
Grüße Medlan