Ich habe ungefähr 3000 verschiedene Dateien, die ich organisieren und zu verschiedenen Zeiten während des Spiels abrufen muss.
Ich habe meine eigene Struktur von Variablen erstellt. Ich habe überlegt, ein "Wörterbuch" zu erstellen zu Beginn meiner Anwendung und einfach alle meine Dateien vor dem Spielstart laden.
Ich frage mich über die Leistung: Wird ein Wörterbuch mit so vielen Einträgen dazu führen, dass meine Anwendung langsam ist? Würde ein großes Wörterbuch "TryGetValue" und "ContainsKey" langsamer laufen lassen?
Danke für den Rat!
TryGetValue und ContainsKey sollten bei dieser Größe ziemlich schnell sein, solange der Schlüssel gut verteilt ist.
Ein Dictionary hat eine indexierbare Anzahl von "Buckets". Wenn ein Wert durch einen Schlüssel hinzugefügt oder gesucht wird, wird der von GetHashCode () zurückgegebene Wert erneut verwendet, um ihn erneut zu verkleinern, damit er kleiner als die Anzahl der Buckets ist (im Allgemeinen etwas Einfaches wie Modulo, aber die Implementierung ist nicht definiert). und schaue in den entsprechenden Eimer.
Der Bucket enthält derzeit null oder mehr Elemente. Das Wörterbuch vergleicht jedes Element mit dem Schlüssel mithilfe von .Equals ().
Das erste Bit zum Finden des richtigen Eimers wird in der konstanten Zeit O (1) sein. Das zweite Bit des Vergleichs des Schlüssels mit den Schlüsseln im Bucket wird in der linearen Zeit O (n) sein, wobei n sich nur auf die Anzahl der Elemente in diesem Bucket bezieht, nicht in der gesamten Sammlung.
Generell sollte es in jedem Bucket nur sehr wenige Elemente geben (die Anzahl der Buckets wird wachsen, um zu versuchen, dies zu halten), so dass die Operation im Wesentlichen konstante Zeit ist.
Wenn jedoch Ihre Hash-Codes schlecht implementiert sind, gibt es viele Schlüssel in demselben Bucket. Die Zeitkomplexität wird näher und näher an O (n) kommen, wie durch das Experimentieren mit einem Objekt mit einem absichtlich schlechten GetHashCode, der jedes Mal nur 0 zurückgibt, gesehen werden kann. Im schlimmsten Fall ist es schlimmer als eine Liste, da eine Liste auch O (n) ist, aber das Wörterbuch hat mehr Overhead.
Bedeutet das, dass Sie sich Sorgen machen sollten? Nein, selbst relativ naive Hashing-Methoden sollten relativ gute Ergebnisse liefern. Wenn Sie einen String-Schlüssel verwenden, wird es wahrscheinlich schon mehr als gut genug sein. Wenn Sie einen einfachen eingebauten Typ verwenden, dann noch mehr.
Wenn Sie jedoch feststellen, dass der Zugriff auf das Wörterbuch langsam ist, dann sollten Sie darauf achten und entweder die GetHashCode () -Methode korrigieren oder einen IEqualityComparer erstellen (mit dem Sie externe Regeln für GetHashCode () und Equals () definieren können) zur Verwendung mit Wörterbüchern, Hashsets usw.).
Am wahrscheinlichsten, 3000 ist nichts, es wird gut.
3000 Einträge paddeln für ein Dictionary<> . Das wird keine Quelle der Verlangsamung sein.
Beim Start werden 3000 verschiedene Dateien in den Speicher eingelesen, andererseits wird langsam sein. Sie werden viel besser dran sein, wenn Sie Dateien nur zu dem Zeitpunkt in den Speicher lesen, zu dem sie benötigt werden, aber sie für nachfolgende Zugriffe im Speicher behalten.
Nein, wird es nicht. Es wird Speicher verbrauchen, aber TryGetValue und ContainKey sollten ziemlich schnell sein, da ein Wörterbuch eine Hashtabelle ist und der Zugriff auf die Elemente durch den Schlüssel konstant ist und nicht von der Anzahl der Elemente abhängt.
Wenn der Hashcode-Algorithmus für den Dictionary-Schlüsseltyp verwendet wird, werden die Hashcodes relativ gleichmäßig über den Int32-Bereich verteilt. Hashcode-Lookup wird von der Dictionary-Größe nicht beeinflusst.
Weitere Informationen finden Sie Ссылка .
Es gibt eine Grenze, aber 3000 ist nicht annähernd. Dictionary<> verwendet Object.GetHashCode() , um seine Schlüssel zu oraginisieren, wodurch int zurückgegeben wird. Daher können Sie vor einer Kollision maximal 2^32 (4.294.967.296) Schlüssel speichern. Aufgrund der Art und Weise, wie die Hash-Codes von .Net berechnet werden, wird es wahrscheinlich viele Kollisionen geben, wenn Sie sich dieser magischen Zahl nähern.
Das Hinzufügen weiterer Schlüssel verlangsamt TryGetValue und ContainsKey nicht - sie sind O(1) -Operationen.
Wörterbücher in .NET verwenden ein Hashtabellen-Suchschema, sodass das Hinzufügen von Einträgen nur sehr geringe Auswirkungen auf die Suchleistung hat. Das einzige Problem, das Sie haben werden, könnte Speicherverbrauch sein. Ein Wörterbuch mit 3000 Elementen verbraucht ungefähr das 3000-fache des Speichers, der vom Schlüssel verwendet wird, plus die Werttypen. Wenn es nur eine einfache Struktur ohne riesige binäre Blobs ist, ist 3000 geradezu winzig.
Wie bei den meisten Dingen mit Computern (und insbesondere mit der Leistung), "It Depends (tm)"
Alles hängt von der Implementierung des Dictionary ab.
Es könnte als ein binärer Baum gemacht werden, in diesem Fall sollte das Nachschlagen O (log2 N) sein, was bedeutet, dass die Suchzeit langsam wächst, wenn die Größe des Wörterbuchs wächst.
Es könnte als eine Hash-Tabelle gemacht werden, die theoretisch O (1) ist, was bedeutet, dass ein Nachschlagen immer die gleiche Menge an Zeit braucht, unabhängig von der Größe des Wörterbuchs, aber das ist die Theorie und hängt davon ab über die Anzahl der Buckets und die Qualität des Hash-Codes. Viele Items enden im selben Bucket und erfordern eine lineare Suche, was sich mit dem Wachstum des Dictionary erheblich verlangsamt.
Das Wörterbuch müsste jedoch um mehrere Größenordnungen über 3000 hinaus wachsen, bevor Sie einen merklichen Unterschied sehen.
Tags und Links c# silverlight performance dictionary idictionary