C# - Binäre Bäume-und Wörterbücher

Dachte ich, dass die BST waren soll
mehr Speicher effizient, aber es scheint
dass ein Knoten des Baumes erfordert
mehr bytes als ein Eintrag in einer
Wörterbuch. Was gibt? Gibt es eine
Punkt, an dem BST-s sind besser als
Wörterbücher?

Habe ich persönlich noch nie gehört, solch ein Prinzip. Sogar noch, es ist nur ein allgemeiner Grundsatz, nicht eine kategorische Tatsache tief in das Gewebe des Universums.

Allgemein, Wörterbücher sind wirklich nur ein schicker wrapper um ein array von verknüpften Listen. Fügen Sie in das Wörterbuch etwas wie:

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

So seine fast O(1) - operation. Das Wörterbuch verwendet O(internalArray.Länge + n) Speicher, wobei n die Zahl der Elemente in der Auflistung.

Im Allgemeinen BSTs umgesetzt werden können, wie:

• verknüpfte Listen, die mit O(n) Speicherplatz, wobei n die Anzahl der Elemente in der Sammlung.
• arrays, die O(2^h - n) Raum, wo h die Höhe des Baumes und n die Anzahl der Elemente in der Auflistung.
  • Seit rot-schwarz-Bäume haben ein begrenztes Höhe von O(1.44 * n), eine array-Implementierung sollte ein begrenzter Speicherauslastung von etwa O(2^{1.44 n} - n)

Verschiedenheit der C5 TreeDictionary ist implementiert mit arrays, welche wahrscheinlich verantwortlich für die verschwendeten Speicherplatz.

Was gibt? Gibt es einen Punkt, an dem
BST-s sind besser als Wörterbücher?

Wörterbücher haben einige unerwünschte Eigenschaften:

• Kann es nicht genug sein continugous Blöcke von Speicher zu halten, Ihr Wörterbuch, auch wenn die Anforderungen an den Arbeitsspeicher sind sehr viel weniger als die insgesamt verfügbaren RAM.

• Auswertung der hash-Funktion eine beliebig lange Zeitspanne. Zeichenfolgen, zum Beispiel, verwenden den Reflektor zu prüfen, die System.String.GetHashCode Methode -- Sie werden bemerken, hashing ein string immer in O(n) Zeit, was bedeutet, es kann erhebliche Zeit dauern, sehr lange strings. Auf der Seite, Vergleich von strings auf Ungleichheit fast immer schneller als hashing, da kann es erfordern, dass man sich bei den ersten paar chars. Seine ganz möglich, um den Baum einfügt, um schneller als Wörterbuch einfügt, wenn die hash-code-Auswertung zu lange dauert.

  • Int32 ist GetHashCode Methode ist buchstäblich nur return this, so dass Sie würde hardpressed zu finden, ein Fall, wo ein int hashtable mit keys ist langsamer als ein Baum Wörterbuch.

RB Bäume haben einige wünschenswerte Eigenschaften:

• Finden Sie/entfernen Sie die Min-und Max-Elementen in O(log n) Zeit, im Gegensatz zu O(n) Zeit mit einem Wörterbuch.

• Wenn ein Baum wird implementiert als verkettete Liste statt einem array, der Baum ist in der Regel mehr Raum effizienter als ein Wörterbuch.

• Ebenfalls, seine lächerlich einfach zu schreiben, unveränderliche Versionen von Bäumen, die Unterstützung von insert - /lookup/löschen in O(log n) Zeit. Wörterbücher nicht passen gut zu der Unveränderlichkeit, da müssen Sie kopieren die gesamte interne array-für jeden Betrieb (tatsächlich, ich haben gesehen, einige array-basierte Implementierungen von unveränderlich finger-Bäume, eine Art Allzweck-dictionary-Datenstruktur, aber die Umsetzung ist sehr Komplex).

• Können Sie Durchlaufen aller Elemente eines Baumes in sortierter Reihenfolge in der ständigen Platz-und O(n) Zeit, während Sie brauchen, um zu dump eine hash-Tabelle in ein array und sortiert es den gleichen Effekt zu erhalten.

So, die Wahl der Datenstruktur hängt wirklich davon ab, welche Eigenschaften, die Sie benötigen. Wenn Sie wollen einfach nur eine ungeordnete Tasche und können garantieren, dass Ihre hash-Funktion bewerten, schnell, gehen mit ein .Net-Wörterbuch. Wenn Sie eine Tasche bestellt, oder haben eine langsam Laufenden hash-Funktion, gehen Sie mit TreeDictionary.

Mir scheint, du machst eine vorzeitige Optimierung.

Ich würde Ihnen vorschlagen, ist eine Schnittstelle zu erstellen, zu isolieren, die Struktur, die Sie tatsächlich verwenden, und implementieren Sie das interface mit dem Wörterbuch (das scheint am besten zu funktionieren).

Wenn der Speicher/performance zum Thema wird (was wahrscheinlich nicht für 20k - zahlen), dann können Sie andere interface-Implementierungen, und überprüfen Sie, welche works Bestleistungen. Sie nicht brauchen, um zu ändern, fast alles in der rest des Codes (es sei denn, die Implementierung, die Sie verwenden).

Sind Sie nicht zu vergleichen "äpfel mit äpfeln", eine BST-geben Sie eine bestellt Darstellung, während ein Wörterbuch erlaubt Ihnen, eine Suche auf ein Schlüssel-Wert-paar (in deinem Fall ).

Ich würde nicht erwarten, viel Größe in den Speicher-footprint zwischen den 2, aber das Wörterbuch wird Ihnen eine viel schnellere Suche. Finden Sie ein Element in einem BST du (potentiell) brauchen zum Durchlaufen der gesamten Baumstruktur. Aber dazu ein dictnary Suche Sie einfach lookup basierend auf dem Schlüssel.