Ich bin in einem Programm, das ich für meine Arbeit schreibe, auf eine Mauer gestoßen. Sie müssen den Kontext nicht speziell kennen, aber kurz gesagt, ich habe zwei Sammlungen von ungefähr ~ 650k Datensätzen.
Nehmen wir an, dass die Sammlung A die richtige ist, und die Sammlung B ist diejenige, von der ich weiß, dass sie falsch ist.
Sammlung B enthält ein komplexes Objekt, das eine Eigenschaft des gleichen Typs wie die Elemente in Sammlung A hat (mit anderen Worten, es sieht ungefähr so aus):
%Vor%Mein Problem ist, dass ich im Grunde über A aufzählen muss, um zu sehen, ob das aktuelle Element von A in einem komplexen Objekt in B existiert; Wenn es nicht existiert, muss ich ein komplexes Objekt erstellen, das dieses Element (unter anderem) kapselt.
Das Problem tritt auf, wenn ich feststelle, dass beide Listen 650.000 Elemente lang sind, ca. Ich kann den Datensatz nicht reduzieren; Ich muss diese 650.000 verwenden. Im Moment habe ich ICollection.Contains() verwendet und eine (naive) Implementierung der Binärsuche versucht, aber das dauert einfach viel zu lange.
Hast du Vorschläge für mich?
EDIT: Wenn es hilft, implementiert T IComparable. EDIT2: Etwas mehr Kontext: Der IEnumerable wird von einer DataTable mithilfe von Linq To Objects abgerufen.
%Vor%Aus Gründen der Vollständigkeit, falls diese Frage archiviert wird und jemand anderes dieses Problem beheben muss, sah meine aktuelle Implementierung ein bisschen so aus.
%Vor%Dank Cosmin ist dieses Problem jetzt gelöst und die fertige Implementierung ist dies: Liste erwartet = neue Liste (); DateTime current = RoundSeconds (neue DateTime (start.Time.Ticks));
%Vor%Schritt für Schritt:
O(1) , um eine schnell durchsuchbare Liste von T zu erstellen, die sich bereits in der zweiten Sammlung befinden. Darf ich vorschlagen HashSet<T>
T aus dem ersten Schritt in die Sammlung ein. O(1) ist, hast du jetzt eine O(n) Lösung. Hier ist eine Klasse, die diesen Algorithmus als generische Erweiterungsmethode implementiert, um sie LINQ-freundlicher zu machen. Gemacht nimm man seine Argumente als IEnumerable<T> und return IEnumerable<T> , machte keine Annahmen über die Typen ( T und Complex ). In meinem Test verwende ich eine Liste von Tuple<int,int> als einen komplexen Typ und eine einfache int als den einfachen Typ. Die Konsolenanwendung füllt List<Tuple<int,int>> mit 600000 Werten und setzt 100000 Werte in die einfache List<int> , die einen Enumerator verwendet, um alle einfachen Werte zu zählen, die nicht in List<Tuple<int,int>> gefunden wurden. Es ist so schnell, dass du keine Chance hast es zu sehen, wenn es funktioniert. Wenn du F5 drückst, zeigt es nur das Ergebnis an.
Ich würde vorschlagen, Ihre komplexen Objekte in einem Dictionary zu speichern, indem Sie die A-Type-Eigenschaft als Schlüssel verwenden. Dann können Sie sehen, ob ein Element in A sehr schnell im Dictionary existiert. Jede Suchoperation wird O (1) sein, und die Gesamtleistung sollte O (n) sein.
Alternativ können Sie .ToLookup () für Ihr vorhandenes IEnumerable aufrufen und den Schlüssel und Wert in einem Lambda-Ausdruck erstellen. Der zurückgegebene ILookup sollte perfekt für Ihre Bedürfnisse sein (d. H. Nach Werten von A suchen). Der zusätzliche Vorteil hier ist, dass wenn Sie mehrere komplexe Objekte mit A haben, erhalten Sie eine Sammlung von ihnen zurück, wenn Sie die Suche verwenden.
Wenn ich Ihre Anforderung verstanden habe, dann funktioniert dieser Code gut. Ich habe es auf 6.5m Datensätze für beide Sammlungen erhöht und es in 11 Sekunden abgeschlossen. Die Reduzierung auf 650k Datensätze dauert weniger als eine Sekunde.
%Vor%UPDATE: Hören Sie zuallererst auf, die Datasets zu verwenden. Ich schlage vor, Sie verwenden Linq zu SQL oder Entity Framework.
Versuchen Sie Folgendes:
%Vor%Das sollte schneller sein, aber messen.
Dann probiere
aus %Vor%Und nochmals messen.
Stellen Sie sicher, dass der Typ der Objekte in A GetHashCode() und Equals(object) correcty und effizient überschreibt. Insbesondere GetHashCode() sollte eine hohe Wahrscheinlichkeit haben, dass verschiedene Objekte einen anderen Hash-Code haben und trotzdem schnell sind.
UPDATE: Da wir jetzt wissen, dass der Typ der Objekte in A DateTime ist, ist die Anforderung für GetHashCode() und Equals(object) OK.
Der Code wird
%Vor% Wenn Sie Listen mit demselben Schlüssel sortieren, können Sie beide gleichzeitig durchlaufen. Auf diese Weise konnte ich die Zeit auf weniger als die von contains oder except und sogar noch weniger als die toLookup-Zeiten, die ich sah, heruntersetzen.
Um die Testdaten zu erzeugen, habe ich folgendes gemacht:
%Vor%