Leistung von Dictionary <string, Objekt> vs Liste <string> + BinarySearch

Question

Ich habe eine benutzerdefinierte Leistung Timer-Implementierung. Kurz gesagt ist es eine statische Datensammlung, die die Ausführungsdauer einiger Codepfade speichert. Um bestimmte Messungen zu identifizieren, benötige ich eine Sammlung von benannten Objekten mit schnellem Zugriff auf das Datenelement nach Namen, d. H. Eine string von mittlerer Länge wie 20-50 Zeichen.

Einfache Möglichkeit, dies zu tun könnte ein Dictionary<string, MyPerformanceCounter> mit Zugriff durch Schlüssel, die die Zähler-ID ist.

Wie wäre es mit einem List<MyPerformanceCounter>, auf den über List<T>.BinarySearch und List.Insert zugegriffen werden konnte. Hat es eine Chance, mehr lineare Leistung zu haben, wenn ich mehrere hundert Zähler haben müsste?

Unnötig zu sagen, ich brauche den Zugriff auf die richtige MyPerformanceCounter um so schnell wie möglich zu sein, wie es bei Raten von Dutzenden von Tausenden pro Sekunde aufgerufen wird und sollte Code-Ausführung so wenig wie möglich beeinflussen.

Neue Zähler werden relativ selten angehängt wie einmal pro Sekunde.

Answer 1

Es gibt mehrere potenziell nicht-O (1) Teile für ein Wörterbuch.

Die erste erzeugt einen Hash-Code. Wenn Ihre Strings lang sind, müssen Sie jedes Mal einen Hash der Zeichenfolge generieren, wenn Sie sie als Schlüssel in Ihrem Wörterbuch verwenden. Das Wörterbuch speichert die Hashes der vorhandenen Schlüssel, so dass Sie sich keine Gedanken darüber machen müssen, nur was Sie übergeben. Wenn die Zeichenfolgen kurz sind, sollte Hashing schnell sein. Lange Strings brauchen wahrscheinlich länger zum Hash-Vorgang als ein String-Vergleich. Hashing wirkt sich sowohl auf Lese- als auch auf Schreibvorgänge aus.

Der nächste nicht konstante Teil eines Wörterbuchs ist, wenn Sie Hash-Kollisionen haben. Sie speichert intern eine verknüpfte Liste von Werten mit demselben Hash-Bucket und muss den Schlüssel mit jedem Element in diesem Bucket vergleichen und vergleichen, wenn Hash-Kollisionen auftreten. Da Sie Strings verwenden und sehr viel Mühe darauf verwenden, eine gute String-Hashing-Funktion zu entwickeln, sollte dies kein allzu großes Problem darstellen. Hash-Kollisionen verlangsamen sowohl Lese- als auch Schreibvorgänge.

Der letzte nicht konstante Teil ist nur während des Schreibvorgangs. Wenn der interne Speicher nicht mehr ausreicht, muss er die gesamte Hash-Tabelle intern neu berechnen. Dies ist immer noch viel schneller als Array-Inserts (wie eine Liste <> tun würde). Wenn Sie nur ein paar hundert Dinge haben, wird Sie das bestimmt nicht beeinflussen.

Eine Liste auf der anderen Seite wird einen Durchschnitt von N/2 Kopien für jede Einfügung und log2 (N) für jede Suche benötigen. Wenn die Zeichenfolgen nicht alle ähnliche Präfixe haben, werden die einzelnen Vergleiche viel schneller als das Wörterbuch sein, aber es wird viel mehr von ihnen geben.

Also, wenn Ihre Strings ziemlich lang sind, Hashing ineffizient zu machen, wird ein Wörterbuch Ihnen bessere Leistung geben.

Wenn Sie etwas über die Art Ihrer Zeichenfolgen wissen, können Sie eine spezifischere Datenstruktur schreiben, die für Ihr Szenario optimiert ist. Wenn ich zum Beispiel wüsste, dass alle Strings mit einem ASCII-Großbuchstaben beginnen und jeder zwischen 5 und 10 Zeichen lang ist, könnte ich ein Array von 26 Arrays erstellen, eines für jeden Buchstaben, und dann enthält jedes dieser Arrays 6 Listen , eine für jede Saitenlänge. Etwas wie folgt aus:

List<string>[][] lists = new List<string>[26][6]; 
foreach (string s in keys) 
{ 
    var list = lists[s[0] - 'A'][s.Length - 5]; 
    if (list == null) 
    { 
     lists[s[0] - 'A'][s.Length] = list = new List<string>(); 
    } 
    int ix = list.BinarySearch(s); 
    if (ix < 0) 
    { 
     list.Insert(~ix, s); 
    } 
} 

Dies ist die Art von Sache, die Sie tun, wenn Sie sehr spezifische Informationen über haben, welche Art von Daten, die Sie zu tun haben. Wenn Sie keine Vermutungen anstellen können, ist die Verwendung eines Wörterbuchs wahrscheinlich die beste Wahl.

Sie könnten auch in Betracht ziehen, OrderedDictionary zu verwenden, wenn Sie binäre Suchroute gehen, glaube ich, dass es intern einen binären Suchbaum verwendet. https://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary%28v=vs.110%29.aspx

Answer 2

Ich glaube, Sie sollten die Dictionary<string, MyPerformanceCounter> verwenden.

Für kleine Datensätze wird die Liste eine bessere Leistung haben. Da jedoch mehr Elemente benötigt werden, wird das Dictionary deutlich überlegen.

• Die Zeit für eine Dictionary erforderlich: O (1)konstante Zeit Komplexität.
• Die Liste hat eine O (N)lineare Zeitkomplexität.

Sie könnten versuchen, Hashtable oder SortedDictionary, aber ich denke, dass Sie noch Dictionary verwenden sollten.

ich einen Link mit Benchmarks und Richtlinien hier: http://www.dotnetperls.com/dictionary-time

Ich hoffe, das Ihnen hilft.