Optimierung Lookups: Dictionary Schlüsselsuche vs. Array-Index-Lookups

Question

Ich schreibe ein 7-Karten-Poker Hand Evaluator als eine meiner Lieblingsprojekte. Bei dem Versuch, seine Geschwindigkeit zu optimieren (Ich mag die Herausforderung), war ich schockiert zu finden, dass die Leistung von Dictionary Schlüssel-Lookups ziemlich langsam war im Vergleich zu Array-Index-Lookups.

Zum Beispiel lief ich diesen Beispielcode, der 52 über alle aufzählt wählen 7 = 133784560 möglich 7 Karten Hände:

var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
    intDict.Add(i, i);  
    intList.Add(i);
}

int result;

var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);

, welche Ausgänge:

time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms

Ist diese Art von Verhalten zu erwarten (Leistungsabfall um den Faktor 8)? IIRC, ein Wörterbuch hat im Durchschnitt O (1) Lookups, während ein Array Worst-Case-O (1) Lookups, so kann ich die Array-Lookups erwarten, schneller zu sein, aber nicht so viel!

Ich bin zur Speicherung Schürhakenhandklassifizierungen in einem Wörterbuch. Ich nehme an, wenn dies so schnell ist wie die Wörterbuch-Lookups werden kann, muss ich mein Ansatz und die Nutzung Arrays statt überdenken, obwohl die Rankings der Indizierung wird ein wenig schwierig bekommen und ich werde wahrscheinlich eine andere Frage danach fragen müssen.

Answer 1

Sie nicht vergessen, dass Big-O-Notationen nur sagt, wie sich die Komplexität in Bezug auf die Größe wächst (etc.) - es keinen Hinweis auf die konstanten Faktoren nicht geben beteiligt. Deshalb manchmal sogar ein linearer Suche für Schlüssel ist schneller als ein Wörterbuchsuche, wenn es ausreichend wenig Tasten. In diesem Fall tun Sie nicht einmal eine Suche mit dem Array obwohl - um nur gerade Indexierungsvorgang

.

Für gerade Index-Lookups, Arrays sind im Grunde ideal - es ist nur ein Fall von

pointer_into_array = base_pointer + offset * size

(Und dann eine Pointer-Dereference).

ein Wörterbuch-Lookup durchführen ist relativ kompliziert - sehr schnell im Vergleich mit (sagen wir) eine lineare Lookup durch Schlüssel, wenn es viele Schlüssel sind, aber viel komplizierter als eine gerade Array-Lookup. Es hat die Hash-Wert des Schlüssels zu berechnen, dann arbeiten Sie heraus, welche Eimer, der in sein sollte, möglicherweise mit doppeltem Hashes beschäftigen (oder doppelten Eimer) und dann prüfen, auf Gleichheit.

Wie immer wählen Sie die richtige Datenstruktur für die Job -. Und wenn Sie wirklich weg mit nur Indizierung in ein Array bekommen (oder List<T>), dann ja, das unglaublich schnell sein wird,

Answer 2

  

Ist diese Art von Verhalten zu erwarten (Leistungsabfall um den Faktor 8)?

Warum nicht? Jeder Array-Lookup fast intantaneous / negligeable ist, während ein Wörterbuchsuche kann mindestens einen zusätzlichen Unterprogramm-Aufruf muß.

Der Punkt ihrer beide sind O (1) bedeutet, dass selbst wenn Sie 50-mal in jeder Kollektion mehr Einzelteile haben, ist die Leistungsabnahme nach wie vor nur ein Faktor von was auch immer es ist (8).

Answer 3

Etwas könnte ein Jahrtausend nehmen, und noch sein O (1).

Wenn Sie einstufiges durch diesen Code in der Demontage Fenster, werden Sie schnell kommen zu verstehen, was der Unterschied ist.

Answer 4

Wörterbuch Strukturen sind besonders nützlich, wenn der Schlüsselraum ist sehr groß und nicht in eine stabile abgebildet werden können, sequenziert Reihenfolge. Wenn Sie Ihre Schlüssel in eine einfache ganzen Zahl in einem relativ kleinen Bereich umwandeln können, werden Sie hart gedrückt werden, um eine Datenstruktur zu finden, die als ein Array besser abschneiden werden.

Auf einer Implementierung zur Kenntnis; in .NET, Wörterbücher sind im wesentlichen hashables. Sie können etwas ihre Schlüssel-Lookup-Leistung verbessern, indem sichergestellt wird, dass Ihre Schlüssel in einen großen Raum mit eindeutigen Werten Hash. Es sieht aus wie in Ihrem Fall, Sie eine einfache ganze Zahl als Schlüssel verwenden (was ich Hashes seinen eigenen Wert glauben.) - so dass vielleicht die best Sie tun können,

Answer 5

Ein Array-Lookup ist über das schnellste, was Sie tun können - im Wesentlichen alle es ist ein einzelnes Bit von Zeigerarithmetik ist von Anfang des Arrays auf das Element gehen Sie finden wollten. Auf der anderen Seite ist das Wörterbuch-Lookup wahrscheinlich etwas langsamer zu sein, da es Hashing und Sorge zu tun braucht, um sich mit den richtigen Eimer zu finden. Obwohl die erwartete Laufzeit auch für O (1) - die algorithmischen Konstanten sind größer, so wird es langsamer sein

.

Answer 6

Willkommen bei Big-O-Notation. Man muss immer bedenken, dass es ein konstanter Faktor ist beteiligt.

Doing ein Dict-Lookup ist natürlich viel teurer als ein Array-Lookup.

Big-O nur erfahren Sie, wie Algorithmen Skala. Die doppelte Menge an Lookups und sieht, wie die Zahlen ändern. Sowohl um die zweimal Zeit in Anspruch nehmen sollte

Answer 7

Die Kosten für ein Element des Abrufens von einem Wörterbuch ist O (1) , aber das ist, weil ein Wörterbuch als Hash-Tabelle implementiert ist - so müssen Sie zuerst den Hash-Wert berechnen zu wissen, welches Element zurückzukehren. Hashtables sind oft nicht so effizient - aber sie sind für große Datenmengen gut, oder Datensätze, die eine Menge einzigartigen-Hash-Werte

.

Die Liste (abgesehen von einem Müllwort zu sein verwendet, eher ein Array dercribe als eine verkettete Liste!) Wird schneller sein, da sie den Wert zurückkehren, indem Sie direkt das Element Berechnung zurückgegeben werden sollen.