Was ist der effizienteste Weg, um Look-up-Tabelle in C # zu tun

Question

Was ist der effizienteste Weg, um Look-up-Tabelle in C # zu tun

Ich habe eine Nachschlagetabelle. So ähnlich wie

0 "Thing 1"
1 "Thing 2"
2 "Reserved"
3 "Reserved"
4 "Reserved"
5 "Not a Thing"

Wenn also jemand "Ding 1" oder "Ding 2" will, gibt er 0 oder 1 ein. Aber er kann auch etwas anderes eingeben. Ich habe 256 solcher Dinge und vielleicht 200 davon sind reserviert.

Wie lässt sich dies am effizientesten bewerkstelligen?

• Eine String-Array- oder Wörterbuchvariable, die alle Werte enthält. Und dann nehmen Sie die ganze Zahl und geben den Wert an dieser Stelle zurück.

Ein Problem, das ich mit dieser Lösung habe, sind die vielen "reservierten" Werte. Ich möchte diese redundanten "reservierten" Werte nicht erstellen. Oder ich kann eine if-Anweisung für alle verschiedenen "reservierten" Stellen haben, aber es könnten jetzt nur 2-3 sein, vielleicht 2-3, 40-55 und alle verschiedenen Stellen im Byte. Diese if-Anweisung würde schnell unübersichtlich werden

• Die andere Möglichkeit, an die ich gedacht habe, war eine Switch-Anweisung. Und ich würde alle 50ish bekannte Werte haben und würde durch und Standard für die reservierten Werte fallen.

Ich frage mich, ob dies eine Menge mehr Verarbeitung als Erstellen eines String-Arrays oder Wörterbuchs und nur den entsprechenden Wert zurückgeben ist.

• Etwas anderes? Gibt es noch einen anderen Weg, den man in Betracht ziehen könnte?

Answer 1

"Das Abrufen eines Wertes mit Hilfe seines Schlüssels ist sehr schnell, nahezu O(1), da die Klasse Dictionary(TKey, TValue) als Hash-Tabelle implementiert ist."

var things = new Dictionary<int, string>();
things[0]="Thing 1";
things[1]="Thing 2";
things[4711]="Carmen Sandiego";

Answer 2

Der absolut schnellste Weg, um Lookups von Integer-Werten in C# zu tun ist mit einem Array. Dies ist vielleicht besser als die Verwendung eines Wörterbuchs, wenn Sie versuchen, Zehntausende von Suchvorgängen auf einmal durchzuführen. Für die meisten Zwecke ist dies ein Overkill; es ist wahrscheinlicher, dass Sie die Entwicklungszeit als die Prozessorzeit optimieren müssen.

Wenn es sich bei den reservierten Schlüsseln nicht einfach um alle Schlüssel handelt, die nicht in der Nachschlagetabelle enthalten sind (d.h. wenn eine Suche nach einem Schlüssel den gefundenen Wert, einen Nicht-gefunden-Status oder einen reservierten Status zurückgeben kann), müssen Sie die reservierten Schlüssel irgendwo speichern. Sie als Wörterbucheinträge mit magischen Werten zu speichern (z. B. ist der Schlüssel eines Wörterbucheintrags, dessen Wert null ist, reserviert), ist in Ordnung, es sei denn, Sie schreiben Code, der über die Wörterbucheinträge iteriert, ohne sie zu filtern.

Eine Möglichkeit, dieses Problem zu lösen, ist die Verwendung einer separaten HashSet<int> um die reservierten Schlüssel zu speichern, und vielleicht das Ganze in eine Klasse zu packen, z.B.:

public class LookupTable
{
   public readonly Dictionary<int, string> Table { get; }
   public readonly HashSet<int> ReservedKeys { get; }

   public LookupTable()
   {
      Table = new Dictionary<int, string>();
      ReservedKeys = new HashSet<int>();
   }

   public string Lookup(int key)
   {
      return (ReservedKeys.Contains(key))
         ? null
         : Table[key];
   }
}

Sie werden feststellen, dass das Problem des magischen Werts weiterhin besteht. Lookup gibt null zurück, wenn der Schlüssel reserviert ist, und löst eine Ausnahme aus, wenn er nicht in der Tabelle ist - aber zumindest kann man jetzt über Table.Values ohne magische Werte zu filtern.

Answer 3

Wenn Sie viele reservierte (derzeit unbenutzte) Werte haben oder wenn der Bereich der Integer-Werte sehr groß werden kann, dann würde ich ein generisches Wörterbuch (Dictionary) verwenden:

var myDictionary = new Dictionary<int, string>();
myDictionary.Add(0, "Value 1");
myDictionary.Add(200, "Another value");
// and so on

Andernfalls, wenn Sie eine feste Anzahl von Werten haben und nur wenige von ihnen derzeit unbenutzt sind, dann würde ich ein String-Array (string[200]) verwenden und die reservierten Einträge auf null setzen/lassen.

var myArray = new string[200];
myArray[0] = "Value 1";
myArray[2] = "Another value";
//myArray[1] is null

Answer 4

Sehen Sie sich das HybridDictionary an. Es passt den zugrunde liegenden Speichermechanismus automatisch an die Größe an, um die größtmögliche Effizienz zu erzielen.

http://msdn.microsoft.com/en-us/library/system.collections.specialized.hybriddictionary.aspx

Answer 5

Die eingebaute Wörterbuch Objekt (vorzugsweise ein allgemeines Wörterbuch) wäre hierfür ideal und ist speziell für den schnellen/effizienten Abruf der Werte zu den Schlüsseln konzipiert.

Aus dem verlinkten MSDN-Artikel:

Abrufen eines Wertes durch sehr schnell, nahe an O(1), weil das Dictionary<(Of <(TKey, TValue>)>) Klasse als Hashtabelle implementiert ist.

Was Ihre "reservierten" Schlüssel betrifft, so würde ich mir darüber keine Sorgen machen, wenn es sich nur um ein paar hundert Schlüssel/Werte handelt. Es ist nur, wenn Sie Dutzende, vielleicht Hunderttausende von "reservierten" Schlüssel/Werte erreichen, dass Sie etwas effizienter implementieren möchten.

In diesen Fällen wäre der effizienteste Speichercontainer dann wahrscheinlich die Implementierung eines Spärliche Matrix .