Was ist die beste Datenstruktur in .NET für von String-Schlüssel oder numerischen Index Look-up?

Question

Ich interessiere mich für die idealste Datenstruktur (für Leistung und Benutzerfreundlichkeit), aus denen Werte können durch String-Schlüssel oder Index abgerufen werden. Wörterbuch funktioniert nicht, weil Sie durch den Index nicht wirklich abrufen kann. Irgendwelche Ideen?

Answer 1

Sie möchten die OrderedDictionary Klasse . Sie müssen den System.Collections.Specialized Namespace enthalten:

    OrderedDictionary od = new OrderedDictionary(); 
    od.Add("abc", 1); 
    od.Add("def", 2); 
    od.Add("ghi", 3); 
    od.Add("jkl", 4); 

    // Can access via index or key value:      
    Console.WriteLine(od[1]);       
    Console.WriteLine(od["def"]);

Answer 2

Es gibt System.Collections.ObjectModel. KeyedCollection , die aus Sammlung stammt . Retrieval ist O (1) .

class IndexableDictionary<TItem> : KeyedCollection<string, TItem>
 { Dictionary<TItem, string> keys = new Dictionary<TItem, string>();

   protected override string GetKeyForItem(TItem item) { return keys[item];}

   public void Add(string key, TItem item) 
    { keys[item] = key;
      this.Add(item);
    }
 }

Answer 3

Ein Wort der Warnung. Die OrderedDictionary hat wirklich schlechte Leistungseigenschaften für die meisten Operationen außer Einsetzen und Lookup: Sowohl die Entfernung und Änderung eines Wertes kann eine lineare Suche der gesamten Liste erfordern, was zu einer Laufzeit O ( n ). (Für die Modifikation, das hängt davon ab, ob der Zugriff erfolgte durch den Index oder Schlüssel).

Für die meisten Operationen mit angemessenen Mengen an Daten, das ist völlig unakzeptabel. Darüber hinaus speichert Elemente die Datenstruktur sowohl in einem linearen Vektor und in einer Hash-Tabelle, in einigem Speicheraufwand zur Folge hat.

Wenn Abruf durch Index geschieht nicht allzu oft, ein SortedList oder SortedDictionary haben viel bessere Leistungseigenschaften (Zugang durch den Index durch die ElementAt Erweiterungsmethode erreicht werden kann ).

Wenn auf der anderen Seite den Zugriff Index die Norm ist, dann stoppen Wörterbuch Datenstrukturen alltogether und einfach speichern Sie Ihre Werte in einem List<KeyValuePair<TKey, TValue>> . Obwohl dies eine lineare Suche für den Zugriff durch Schlüssel bedeutet, alle anderen Operationen sind sehr billig und die Gesamtleistung ist in der Praxis schwierig zu schlagen.

/ EDIT: Natürlich, letzteres ist auch eine Wörterbuch Datenstruktur im theoretischen Sinne. Man könnte sogar in einer Klasse kapselt die entsprechende Schnittstelle zu implementieren.

Answer 4

Hash basierte Sammlungen (Dictionary, Hashtable, HashSet) sind, weil Sie keinen Index haben, da Sie einen Index wollen, ich würde eine verschachtelte generic:

List<KeyValuePair<K,V>>

Natürlich verlieren Sie die O (1) Key-Lookup, die Sie mit Hashes erhalten.

Answer 5

Ein Wörterbuch könnte mit Linq arbeiten. Obwohl ich weiß, über mögliche Performance-Probleme nicht. Dictionary.ElementAt (Index);

Answer 6

Ich empfehle, mit SortedDictionary oder SortedList . Beide haben O (log n) Suchleistung.

Die Unterschiede sind, wie zitiert aus die MSDN Library :

  

SortedList <(Of   <(TKey, TValue>)>) benötigt weniger Speicher   als SortedDictionary <(Of <(TKey,   TValue>)>).

     

SortedDictionary <(Of <(TKey,   TValue>)>) hat schnellere Einführung und   Entnahmen für unsortierte Daten:   O (log n) im Gegensatz zu O (n) für   SortedList <(Of <(TKey, TValue>)>).

     

Wenn die Liste wird auf einmal bevölkert   von sortierten Daten, SortedList <(Of   <(TKey, TValue>)>) ist schneller als   SortedDictionary <(Of <(TKey,   TValue>)>).

Nach meiner Erfahrung ist SortedDictionary mehr ausreichend für die meisten typischen Geschäftsszenarios, da die Daten in der Regel zunächst unsortiert, wenn Strukturen wie diese verwendet wird, und die Speicher-Overhead von SortedDictionary ist selten kritisch. Aber wenn die Leistung Schlüssel für Sie ist, schlage ich vor, Sie beide implementieren und Messungen tun.

Answer 7

Sie suchen so etwas wie die SortedList-Klasse (hier ist die generische Version sowie ).