Gibt es eine Struktur, die BEIDE dieser Operationen zulässt:
collection.TryGetValue(TKey, out TValue) collection.TryGetKey(TValue, out TKey) In einer besseren Zeit als O (n)?
Mein Problem:
Ich muss im Prinzip in der Lage sein, den Wert des Schlüssels oder value schnell zu erhalten, ohne den Speicher zu duplizieren (zwei Wörterbücher kommen also nicht in Frage).
Sehr wichtige Anmerkung: Alle Schlüssel sind einzigartig und alle Werte sind einzigartig. Mit dieser Information, die ich fühle , sollte es möglich sein, diese Aufgabe zu einem besseren Zeitpunkt zu erledigen als nur O (1) für .TryGetValue und O (n) für .TryGetKey .
BEARBEITEN:
In meinem Fall habe ich eine Zuordnung zwischen strings und ints . Es gibt ~ 650.000 Schlüssel-Wert-Paare von Texten und ihre IDs. Also möchte ich im Grunde die Zeichenfolge mit einer bestimmten ID, aber auch die ID einer bestimmten Zeichenfolge abrufen.
Um besser als O (n) zu werden, müssen Sie ein zweites Wörterbuch verwenden. Aber wie Sie bereits erwähnt sind Sie structs und sind besorgt über die Speichernutzung mit einem zweiten Wörterbuch mit einem Duplikat der Struktur verwendet wird.
Um dies zu umgehen, geben Sie den struct-Wert innerhalb eines Objekts ein und teilen Sie dann das boxed-Objekt in den beiden Wörterbüchern. Wenn Sie erben verwenden von DictionaryBase diese ist eigentlich ziemlich einfach zu implementieren.
Das Dictionary und reverseLookup Worte die gleichen Referenzen teilen, so wird es einen kleineren Speicherbedarf hat als die Verwendung von zwei stark Wörterbücher mit großen structs eingegeben hat.
Ohne eine vollständiges Dictionary<TKey, TValue> Umsetzung zu schreiben, die zwei interne bucket Sammlungen für Schlüssel und Werte und zwei verkettete Listen für die Ketten usees aus dem Eimer Das glaube ich nicht, dass Sie viele bessere Ergebnisse erhalten.
Sie können einen Wrapper für key schreiben, der Schlüssel und Link zu value wrapper und wrapper für value enthalten sollte, der Wert enthalten und auf key wrapper verlinken soll. Und verwende zwei verschiedene HashSet s.
In diesem Fall vermeiden Sie eine Speicherverdopplung. Sie benötigen nur zusätzlichen Speicher für Links.
Tags und Links .net c# collections big-o