Schnellster Weg, um zwei generische Listen auf Unterschiede zu vergleichen

213

Was ist am schnellsten (und am wenigsten ressourcenintensiv), um zwei massive (> 50.000 Elemente) zu vergleichen und als Ergebnis zwei Listen wie die folgenden zu haben:

  1. Elemente, die in der ersten Liste angezeigt werden, jedoch nicht in der zweiten
  2. Elemente, die in der zweiten Liste angezeigt werden, jedoch nicht in der ersten

Derzeit arbeite ich mit der Liste oder IReadOnlyCollection und löse dieses Problem in einer Linq-Abfrage:

var list1 = list.Where(i => !list2.Contains(i)).ToList();
var list2 = list2.Where(i => !list.Contains(i)).ToList();

Aber das funktioniert nicht so gut, wie ich es gerne hätte. Haben Sie eine Idee, dies schneller und weniger ressourcenintensiv zu machen, da ich viele Listen verarbeiten muss?

Frank
quelle

Antworten:

452

Verwendung Except:

var firstNotSecond = list1.Except(list2).ToList();
var secondNotFirst = list2.Except(list1).ToList();

Ich vermute, dass es Ansätze gibt, die tatsächlich geringfügig schneller wären, aber selbst dies wird erheblich schneller sein als Ihr O (N * M) -Ansatz.

Wenn Sie diese kombinieren möchten, können Sie eine Methode mit der obigen und dann eine return-Anweisung erstellen:

return !firstNotSecond.Any() && !secondNotFirst.Any();

Ein Punkt zu beachten ist , dass es ist ein Unterschied in den Ergebnissen zwischen dem ursprünglichen Code in der Frage und die Lösung hier: alle doppelten Elemente , die nur in einer Liste sind , werden nur einmal mit meinem Code gemeldet werden, während sie so viele gemeldet werden würde Zeiten, wie sie im Originalcode vorkommen.

Beispielsweise würden bei Listen von [1, 2, 2, 2, 3]und [1]die "Elemente in Liste1, aber nicht Liste2" den ursprünglichen Code ergeben [2, 2, 2, 3]. Mit meinem Code wäre es einfach so [2, 3]. In vielen Fällen ist das kein Problem, aber es lohnt sich, sich dessen bewusst zu sein.

Jon Skeet
quelle
8
Das ist wirklich ein großer Leistungsgewinn! Danke für diese Antwort.
Frank
2
Ich frage mich nach zwei großen Listen. Ist es nützlich, vor dem Vergleich zu sortieren? oder innerhalb Außer Erweiterungsmethode ist die übergebene Liste bereits sortiert.
Larry
9
@ Larry: Es ist nicht sortiert; Es wird ein Hash-Set erstellt.
Jon Skeet
2
@PranavSingh: Es funktioniert für alles, was eine angemessene Gleichheit aufweist. Wenn Ihr benutzerdefinierter Typ also überschreibt Equals(object)und / oder implementiert IEquatable<T>, sollte dies in Ordnung sein.
Jon Skeet
2
@ k2ibegin: Es wird der Standard-Gleichheitsvergleich verwendet, der eine IEquatable<T>Implementierung oder die object.Equals(object)Methode verwendet. Es hört sich so an, als ob Sie eine neue Frage mit einem minimal reproduzierbaren Beispiel erstellen sollten - wir können Dinge in Kommentaren nicht wirklich diagnostizieren.
Jon Skeet
40

Effizienter wäre Enumerable.Except:

var inListButNotInList2 = list.Except(list2);
var inList2ButNotInList = list2.Except(list);

Diese Methode wird mithilfe der verzögerten Ausführung implementiert. Das heißt, Sie könnten zum Beispiel schreiben:

var first10 = inListButNotInList2.Take(10);

Es ist auch effizient, da es intern a verwendet Set<T>, um die Objekte zu vergleichen. Es funktioniert, indem zuerst alle unterschiedlichen Werte aus der zweiten Sequenz gesammelt und dann die Ergebnisse der ersten gestreamt werden, um zu überprüfen, ob sie zuvor noch nicht gesehen wurden.

Tim Schmelter
quelle
1
Hmm. Nicht ganz aufgeschoben. Ich würde sagen, teilweise aufgeschoben. Ein vollständiges Set<T>wird aus der zweiten Sequenz erstellt (dh es wird vollständig iteriert und gespeichert), und dann werden Elemente ausgegeben, die aus der ersten Sequenz hinzugefügt werden können.
Spender
2
@spender, das ist so, als würde man sagen, dass die Ausführung von Whereteilweise verzögert wird, weil list.Where(x => x.Id == 5)der Wert der Zahl 5zu Beginn gespeichert und nicht träge ausgeführt wird.
JWG
27

Enumerable.SequenceEqual-Methode

Bestimmt, ob zwei Sequenzen gemäß einem Gleichheitsvergleich gleich sind. MS.Docs

Enumerable.SequenceEqual(list1, list2);

Dies funktioniert für alle primitiven Datentypen. Wenn Sie es für benutzerdefinierte Objekte verwenden müssen, müssen Sie es implementierenIEqualityComparer

Definiert Methoden zur Unterstützung des Vergleichs von Objekten auf Gleichheit.

IEqualityComparer-Schnittstelle

Definiert Methoden zur Unterstützung des Vergleichs von Objekten auf Gleichheit. MS.Docs für IEqualityComparer

miguelmpn
quelle
Dies sollte die akzeptierte Antwort sein. Die Frage bezieht sich nicht auf SETS, sondern auf LISTS, die doppelte Elemente enthalten können.
Adrian Nasui
3
Ich sehe nicht ein, wie dies die Antwort sein könnte, da das Ergebnis SequenceEqualeinfach ist bool. Das OP möchte zwei Ergebnislisten - und beschreibt, was sie in Bezug auf festgelegte Operationen wollen: "Elemente, die in der ersten Liste angezeigt werden, aber nicht in der zweiten". Es gibt keinen Hinweis darauf, dass die Reihenfolge relevant ist, während SequenceEqual dies für relevant hält. Dies scheint eine ganz andere Frage zu beantworten.
Jon Skeet
Ja, richtig, anscheinend habe ich diese Frage zu schnell beantwortet und mir den zweiten Teil der Anfrage nicht angesehen ... genau wie die ersten beiden Kommentare ...
Miguelmpn
9

Wenn Sie möchten, dass bei den Ergebnissen die Groß- und Kleinschreibung nicht berücksichtigt wird, funktioniert Folgendes:

List<string> list1 = new List<string> { "a.dll", "b1.dll" };
List<string> list2 = new List<string> { "A.dll", "b2.dll" };

var firstNotSecond = list1.Except(list2, StringComparer.OrdinalIgnoreCase).ToList();
var secondNotFirst = list2.Except(list1, StringComparer.OrdinalIgnoreCase).ToList();

firstNotSecondwürde b1.dll enthalten

secondNotFirstwürde b2.dll enthalten

z.B.
quelle
5

Nicht für dieses Problem, aber hier ist ein Code zum Vergleichen von Listen für gleich und nicht! identische Objekte:

public class EquatableList<T> : List<T>, IEquatable<EquatableList<T>> where    T : IEquatable<T>

/// <summary>
/// True, if this contains element with equal property-values
/// </summary>
/// <param name="element">element of Type T</param>
/// <returns>True, if this contains element</returns>
public new Boolean Contains(T element)
{
    return this.Any(t => t.Equals(element));
}

/// <summary>
/// True, if list is equal to this
/// </summary>
/// <param name="list">list</param>
/// <returns>True, if instance equals list</returns>
public Boolean Equals(EquatableList<T> list)
{
    if (list == null) return false;
    return this.All(list.Contains) && list.All(this.Contains);
}
Pius Einsiedler
quelle
1
Dies ist erforderlich, um benutzerdefinierte Datentypen vergleichen zu können. Dann verwenden SieExcept
Pranav Singh
Mit sortierbaren Typen können Sie wahrscheinlich bessere Ergebnisse erzielen. Dies läuft in O (n ^ 2), während Sie O (nlogn) ausführen können.
Yuvalm2
3

versuche es so:

var difList = list1.Where(a => !list2.Any(a1 => a1.id == a.id))
            .Union(list2.Where(a => !list1.Any(a1 => a1.id == a.id)));
Ali Issa
quelle
13
Dies leidet unter einer schrecklichen Leistung, die einen Scan der zweiten Liste für jedes Element in der ersten erfordert. Kein Downvoting, weil es funktioniert, aber es ist genauso schlecht wie der ursprüngliche Code.
Spender
3
using System.Collections.Generic;
using System.Linq;

namespace YourProject.Extensions
{
    public static class ListExtensions
    {
        public static bool SetwiseEquivalentTo<T>(this List<T> list, List<T> other)
            where T: IEquatable<T>
        {
            if (list.Except(other).Any())
                return false;
            if (other.Except(list).Any())
                return false;
            return true;
        }
    }
}

Manchmal muss man nur wissen, ob zwei Listen unterschiedlich sind und nicht, was diese Unterschiede sind. In diesem Fall sollten Sie diese Erweiterungsmethode zu Ihrem Projekt hinzufügen. Beachten Sie, dass Ihre aufgelisteten Objekte IEquatable implementieren sollten!

Verwendung:

public sealed class Car : IEquatable<Car>
{
    public Price Price { get; }
    public List<Component> Components { get; }

    ...
    public override bool Equals(object obj)
        => obj is Car other && Equals(other);

    public bool Equals(Car other)
        => Price == other.Price
            && Components.SetwiseEquivalentTo(other.Components);

    public override int GetHashCode()
        => Components.Aggregate(
            Price.GetHashCode(),
            (code, next) => code ^ next.GetHashCode()); // Bitwise XOR
}

Was auch immer die ComponentKlasse ist, die hier gezeigten Methoden fürCar nahezu identisch implementiert werden.

Es ist sehr wichtig zu beachten, wie wir GetHashCode geschrieben haben. Um richtig umzusetzen IEquatable, Equalsund GetHashCode muss auf der Instanz Eigenschaften in eine logisch kompatibelen Weise.

Zwei Listen mit demselben Inhalt sind immer noch unterschiedliche Objekte und erzeugen unterschiedliche Hash-Codes. Da diese beiden Listen gleich behandelt werden sollen, müssen wir GetHashCodefür jede Liste den gleichen Wert erzeugen. Dies können wir erreichen, indem wir den Hashcode an jedes Element in der Liste delegieren und alle mit dem standardmäßigen bitweisen XOR kombinieren. XOR ist auftragsunabhängig, daher spielt es keine Rolle, ob die Listen unterschiedlich sortiert sind. Es ist nur wichtig, dass sie nur gleichwertige Mitglieder enthalten.

Hinweis: Der seltsame Name bedeutet, dass die Methode die Reihenfolge der Elemente in der Liste nicht berücksichtigt. Wenn Sie sich für die Reihenfolge der Elemente in der Liste interessieren, ist diese Methode nichts für Sie!

Devon Parsons
quelle
1

Ich habe diesen Code verwendet, um zwei Listen mit Millionen von Datensätzen zu vergleichen.

Diese Methode wird nicht viel Zeit in Anspruch nehmen

    //Method to compare two list of string
    private List<string> Contains(List<string> list1, List<string> list2)
    {
        List<string> result = new List<string>();

        result.AddRange(list1.Except(list2, StringComparer.OrdinalIgnoreCase));
        result.AddRange(list2.Except(list1, StringComparer.OrdinalIgnoreCase));

        return result;
    }
Sathish
quelle
0

Wenn nur ein kombiniertes Ergebnis benötigt wird, funktioniert dies auch:

var set1 = new HashSet<T>(list1);
var set2 = new HashSet<T>(list2);
var areEqual = set1.SetEquals(set2);

Dabei ist T der Typ des Listenelements.

Ali Khaleghi Karsalari
quelle
-1

Mag lustig sein, funktioniert aber für mich

string.Join ("", List1)! = string.Join ("", List2)

Jibz
quelle
wie es hier geschrieben steht, würde es nicht einmal für List <string> oder List <int> funktionieren, da zum Beispiel die beiden Listen 11; 2; 3 und 1; 12; 3 identisch wären, da Sie die Strings nicht mit einigen verbinden eindeutiges Trennzeichen, das kein mögliches Element in der Liste ist. Abgesehen davon ist das Verketten von Zeichenfolgen für eine Liste mit vielen Elementen wahrscheinlich ein Leistungskiller.
SwissCoder
@ SwissCoder: Du liegst falsch, dies ist kein Performacne-Killer für Streicher. Wenn Sie zwei Listen mit 50.000 Zeichenfolgen (jeweils Länge 3) haben, benötigt dieser Algorithmus auf meinem Computer 3 ms. Die akzeptierte Antwort benötigt 7. Ich denke, der Trick ist, dass Jibz nur einen String-Vergleich benötigt. Natürlich muss er ein eindeutiges Trennzeichen hinzufügen.
user1027167
@ user1027167: Ich spreche nicht über den direkten Vergleich von Zeichenfolgen (da dies auch nicht die Frage ist). Durch Aufrufen der .ToString () -Methode aller Objekte in einer Liste mit 50.000 Objekten kann je nach Implementierung eine große Zeichenfolge erstellt werden. Ich denke nicht, dass das der richtige Weg ist. Dann ist es auch riskant, sich darauf zu verlassen, dass ein Zeichen oder eine Zeichenfolge "eindeutig" ist. Der Code wäre so nicht wirklich wiederverwendbar.
SwissCoder
Ok das stimmt. Der Fragesteller fragte nach dem schnellsten Weg, ohne den Datentyp seiner Listen anzugeben. Wahrscheinlich ist diese Antwort der schnellste Weg für den Anwendungsfall des Fragestellers.
user1027167
-3

Ich denke, dies ist eine einfache Möglichkeit, zwei Listen Element für Element zu vergleichen

x=[1,2,3,5,4,8,7,11,12,45,96,25]
y=[2,4,5,6,8,7,88,9,6,55,44,23]

tmp = []


for i in range(len(x)) and range(len(y)):
    if x[i]>y[i]:
        tmp.append(1)
    else:
        tmp.append(0)
print(tmp)
user10915707
quelle
3
Dies ist eine C # -Frage, und Sie haben keinen C # -Code angegeben.
Wai Ha Lee
1
Vielleicht können Sie diese Antwort löschen und in (zum Beispiel) verschieben. Wie kann ich zwei Listen in Python vergleichen und Übereinstimmungen zurückgeben ?
Wai Ha Lee
-4

Dies ist die beste Lösung, die Sie gefunden haben

var list3 = list1.Where(l => list2.ToList().Contains(l));
Fajoui El Mahdi
quelle
1
Das ist eigentlich sehr schlecht, weil es List<T>für jedes Element in ein neues erstellt list1. Auch das Ergebnis wird aufgerufen, list3wenn es nicht a ist List<T>.
Wai Ha Lee