Ich habe eine große Menge Daten mit ~ 1,5 Millionen Einträgen. Jeder Eintrag ist eine Instanz einer Klasse wie dieser:
%Vor%Ich habe eine Liste von Guids (~ 4 Millionen), die ich brauche, um die Namen basierend auf einer Liste von Instanzen der Element-Klasse zu erhalten.
Ich speichere die Element-Objekte in einem Dictionary, aber es dauert ~ 90 Sekunden, um die Daten zu füllen. Gibt es eine Möglichkeit, die Leistung beim Hinzufügen von Elementen zum Wörterbuch zu verbessern? Die Daten haben keine Duplikate, aber ich weiß, dass das Wörterbuch nach Duplikaten sucht, wenn ein neues Objekt hinzugefügt wird.
Die Struktur muss kein Wörterbuch sein, wenn es einen besseren gibt. Ich habe versucht, die Element-Objekte in eine Liste zu stellen, die beim Hinzufügen viel besser war (~ 9 Sekunden). Aber dann, wenn ich nach dem Gegenstand mit einem bestimmten Guid suchen muss, dauert es mehr als 10 Minuten, um alle 4 Millionen Elemente zu finden. Ich habe das mit List.Find () versucht und manuell durch die Liste iteriert.
Auch wenn ich, anstatt System.Guid zu verwenden, alle in String umwandle und ihre String-Repräsentation in den Datenstrukturen ablege, dauert die ganze Operation des Auffüllens des Dictionary und das Auffüllen der Namen auf der anderen Liste nur 10s, dann aber mein Anwendung verbraucht 1,2 GB RAM statt 600 MB, wenn ich sie als System.Guid speichern.
Irgendwelche Ideen, wie man es besser macht?
Ihr Problem ist vielleicht mit "sequentiell" Guid verbunden, wie:
Das Dictionary<,> hat ein Problem mit diesen, weil sie oft das gleiche GetHashCode() haben, also muss es einige Tricks machen, die die Suchzeit von O(1) auf O(n) ändern ... Du kannst es lösen durch Verwendung eines benutzerdefinierten Gleichheitsvergleichs, der den Hash auf eine andere Weise berechnet, wie:
Dann deklarieren Sie einfach das Wörterbuch wie folgt:
%Vor%ein kleiner Test, um den Unterschied zu sehen:
%Vor%und
%Vor% Bei sequentiellem Guid ist der Unterschied in der Anzahl der verschiedenen Hash-Codes erstaunlich:
Jetzt ... Wenn Sie ToByteArray() nicht verwenden möchten (weil es nutzlosen Speicher reserviert), gibt es eine Lösung, die Reflexions- und Ausdrucksbäume verwendet ... Es sollte korrekt mit Mono funktionieren, weil Mono "ausgerichtet" ist "seine Umsetzung von Guid zu der von Microsoft in 2004 , das ist alte Zeit: -)
Andere Lösung, basierend auf "undokumentierter aber funktionierender" Programmierung (getestet auf .NET und Mono):
%Vor% Er verwendet den StructLayout "Trick", um Guid einem Haufen int zu überlagern, schreibt ihn in den Guid und liest den int .
Warum hat Guid.GetHashCode () Probleme mit sequenziellen IDs?
Sehr einfach zu erklären: Von der Referenzquelle ist GetHashCode() :
, also sind die _d , _e , _g , _h , _i , _j byte s nicht Teil des Hash-Codes. Bei der Inkrementierung wird zuerst ein Guid im Feld _k (256 Werte), dann beim Überlauf im Feld _j (256 * 256 Werte, also 65536 Werte) und dann im Feld _i (16777216 Werte ). Durch das Nicht-Hashing der Felder _h , _i , _j zeigt der Hash einer sequentiellen Guid nur 256 verschiedene Werte für einen nicht sehr großen Bereich von Guid (oder maximal 512 verschiedene Werte, wenn die _f Feld wird einmal inkrementiert, wie wenn Sie mit Guid ähnlich wie 12345678-1234-1234-1234-aaffffffff00 beginnen, wobei aa (also "unser" _f ) nach 256 Inkrementen von% auf ab erhöht wird co_de%)
Ich bin nicht, der Dictionary Key ist die ID-Eigenschaft der Element-Klasse und nicht die Element-Klasse selbst. Diese Eigenschaft ist vom Typ System.Guid.
Das Problem mit Guid ist, dass es ein sehr spezielles Konstrukt ist. Zum einen ist es ein struct , nicht ein class . Das Verschieben dieser Sache ist nicht so einfach wie das Bewegen eines Zeigers (technisch ein Handle, aber die gleiche Sache), es beinhaltet das Bewegen des gesamten Speicherblocks herum. Denken Sie daran, dass das .NET-Speichermodell alles kompakt macht, so dass auch andere Blöcke verschoben werden müssen, um Platz zu schaffen.
Wenn Sie sich auch den Quellcode ansehen, werden alle Teile als separate Felder gespeichert. 11 von ihnen! Das sind viele Vergleiche für 1,5 Millionen Einträge.
Was ich tun würde, wäre eine Art alternative Guid -Implementierung ( class , nicht struct !) zu erstellen, die auf effiziente Vergleiche zugeschnitten ist. All das schicke Parsen ist nicht nötig, konzentrieren Sie sich nur auf die Geschwindigkeit. Guids sind 16 Bytes lang, das bedeutet 4 long -Felder. Sie müssen Equals wie gewohnt implementieren (vergleichen Sie die 4 Felder) und GetHashCode als XORing der Felder. Ich bin mir sicher, dass das gut genug ist.
Edit: Beachten Sie, dass ich nicht sage, dass die Framework-Implementierung schlecht ist, es ist einfach nicht gemacht für das, was Sie damit machen wollen. In der Tat ist es für deinen Zweck schrecklich.
Wenn Ihre Daten vorsortiert sind, können Sie List<T>.BinarySearch verwenden. um schnell in der Liste zu suchen. Sie müssen eine Vergleichsklasse erstellen und zum Nachschlagen verwenden.
Benutze es dann
%Vor% Sie können diese ganze Sache in IReadOnlyDictionary<Guid, Element> einschließen, wenn Sie wollen, aber vielleicht brauchen Sie diesen Fall nicht.
Tags und Links c# list dictionary