C # Binary Trees und Wörterbücher

StackOverflow https://stackoverflow.com/questions/2151747

Frage

Ich kämpfe mit dem Begriff der, wenn binäre Suchbäume zu verwenden, und wenn Wörterbücher zu verwenden.

In meiner Anwendung habe ich ein kleines Experiment, das die C5-Bibliothek TreeDictionary verwendet (was ich glaube, ist ein rot-schwarz binärer Suchbaum) und den C # Wörterbuch. Das Wörterbuch war immer schneller auf Add / Findeoperationen und auch immer weniger Speicherplatz verwendet. Zum Beispiel bei 16809 <int, float> Einträgen, verwendete das Wörterbuch 342 KiB, während der Baum 723 KiB verwendet.

Ich dachte, dass BST sollte mehr Speicher effizient sein, aber es scheint, dass ein Knoten des Baumes mehr Bytes als ein Eintrag in einem Wörterbuch erfordert. Was gibt? Gibt es einen Punkt, an dem BST sind besser als Wörterbücher?

Auch als Neben Frage, hat jemanden wissen, ob es eine schnelle + mehr Speicher effiziente Datenstruktur zum Speichern von <int, float> Paaren für Wörterbuchtyp Zugriff als eine der beiden genannten Strukturen?

War es hilfreich?

Lösung

  

Ich dachte, dass BST sollte zu   mehr Speicher effizient, aber es scheint,   daß ein Knoten des Baumes erfordert   mehr Bytes als ein Eintrag in einem   Wörterbuch. Was gibt? Gibt es eine   Punkt, an dem BST sind besser als   Wörterbücher?

Ich habe persönlich nie ein solches Prinzip gehört. Sogar noch, es ist nur ein allgemeiner Grundsatz, keine kategorische Tatsache in dem Gewebe des Universums geätzt.

Im Allgemeinen Wörterbücher ist wirklich nur ein schicker Wrapper um eine Reihe von verknüpften Listen. Sie fügen in das Wörterbuch so 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 sein fast O (1) -Operation. Die Wörterbuch Anwendungen O (internalArray.Length + n) Speicher, wobei n die Anzahl der Elemente in der Auflistung.

Generell BSTs kann als implementiert werden:

  • verketteten Listen, die der Einsatz O (n) -Raum, wobei n die Anzahl Elemente in der Sammlung.
  • Arrays , die Verwendung O (2 h - n) Raum, wo h die Höhe des Baumes ist und n die Anzahl der Elemente in der Sammlung.
    • Da Rot-Schwarz-Bäume eine beschränkte Höhe von O (1,44 * n) haben, eine Array Implementierung sollte eine beschränkte Speichernutzung von etwa O hat (2 1.44n - n)

Odds ist, wird die C5 TreeDictionary Arrays implementiert, die für den verschwendeten Raum wahrscheinlich verantwortlich ist.

  

Was soll das? Gibt es einen Punkt, an dem   BST sind besser als Wörterbücher?

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

  • Es gibt nicht genug continugous Speicherblocks sein kann Ihren Wörterbuch zu halten, auch wenn seine Speicheranforderungen sind viel weniger als als die gesamte verfügbare RAM.

  • die Hash-Funktion auswerten kann eine beliebig lange Zeitspanne dauern. Streicher, zum Beispiel die Verwendung Reflector die System.String.GetHashCode Methode zu untersuchen - Sie werden bemerken, eine Zeichenfolge immer nimmt O (n) Zeit Hashing, was bedeutet es viel Zeit für sehr lange Strings nehmen. Auf der einen Seite, Strings für Ungleichheit Vergleich fast immer schneller als Hashing, da es bei nur die ersten paar Zeichen suchen erfordern. Sein ganz möglich Baumeinsätze schneller als Wörterbuch-Einsätze, wenn Hash-Code-Auswertung zu lange dauert.

    • Int32 des GetHashCode Methode ist buchstäblich nur return this, so dass Sie hardpressed würde einen Fall zu finden, wo eine Hash-Tabelle mit int Schlüssel ist langsamer als ein Baum Wörterbuch.

RB Bäume haben einige wünschenswerte Eigenschaften:

  • Sie können die Min- und Max-Elemente in O (log n) Zeit, im Vergleich zu O (n) Zeit mit einem Wörterbuch finden / entfernen.

  • Wenn ein Baum als verkettete Liste implementiert ist eher als ein Array, der Baum ist in der Regel mehr Platz effizienter als ein Wörterbuch.

  • Ebenso seine lächerlich einfach unveränderliche Versionen von Bäumen zu schreiben, die Stützeinsatz / Nachschlagen / in O (log n) Zeit löschen. Wörterbücher passen sich nicht gut an Unveränderlichkeit, da Sie die gesamte interne Array für jeden Betrieb kopieren müssen (eigentlich ich wurde einige Array-basierte gesehen Implementierungen von unveränderlichen Finger Bäume, eine Art Allzweck-Wörterbuchdaten Struktur, aber die Umsetzung ist sehr komplex).

  • Sie können in sortierter Reihenfolge in konstanten Raum und O (n) Zeit alle Elemente in einem Baum durchlaufen, während Sie eine Hash-Tabelle in ein Array-Dump bräuchten und sortieren sie die gleiche Wirkung zu erhalten.

So hängt die Wahl der Datenstruktur wirklich auf, welche Eigenschaften Sie benötigen. Wenn Sie nur eine ungeordnete Tasche wollen und können garantieren, dass Ihre Hash-Funktion schnell bewerten, geht mit einem .Net Wörterbuch. Wenn Sie eine geordnete Tasche benötigen oder eine langsam laufende Hash-Funktion, geht mit TreeDictionary.

Andere Tipps

Es macht Sinn, dass ein Baumknoten würde mehr Speicher als ein Wörterbucheintrag erforderlich. Einen Binärbaum Knoten Bedarf den Wert zu speichern und sowohl die linken und rechten Teilbäume. Die generische Dictionary<TKey, TValue> wird als eine Hash-Tabelle implementiert, die - Ich gehe davon aus - entweder verwendet eine verknüpfte Liste für jede Schaufel (Wert plus einen Zeiger / Referenz) oder irgendeine Art von Remapping (nur der Wert). Ich würde einen Blick in Reflector haben muß, um sicher zu sein, aber für die Zwecke dieser Frage, die ich glaube nicht, es ist so wichtig.

Die spärliche die Hash-Tabelle, desto weniger effizient in Bezug auf der Lagerung / Speichers. Wenn Sie eine Hash-Tabelle (Wörterbuch) und initialisieren seine Kapazität auf 1 Million, zu erstellen und es nur mit 10.000 Elementen füllen, dann bin ich ziemlich sicher, würde es viel mehr Speicher als ein BST mit 10.000 Knoten auffressen.

Dennoch würde ich nicht über irgendwelche Gedanken zu machen, wenn die Menge von Knoten / Schlüssel ist nur in den Tausenden. Das wird in dem Kilobyte gemessen werden, im Vergleich zu Gigabyte physischem RAM.

Wenn die Frage „warum wollen Sie statt einer Hash-Tabelle einen binären Baum benutzen?“ Dann IMO die beste Antwort ist, dass binäre Bäume bestellt werden, während Hash-Tabellen nicht. Sie können nur eine Hash-Tabelle für Schlüssel suchen, die genau gleich etwas sind; mit einem Baum, können Sie sich für einen Wertebereich, nächsten Wert suchen, usw. Dies ist eine ziemlich wichtige Unterscheidung ist, wenn Sie einen Index oder etwas ähnliches sind zu schaffen.

Es scheint mir, Sie tun eine vorzeitige Optimierung.

Was ich Ihnen vorschlagen würde, ist eine Schnittstelle zu isolieren zu schaffen, die Struktur Sie tatsächlich verwenden, und dann implementieren die Schnittstelle das Dictionary (die Arbeit scheint am besten).

Wenn der Speicher / Leistung ein Problem wird (die wahrscheinlich für nicht 20k- Zahlen), dann können Sie andere Schnittstellenimplementierungen erstellen und überprüfen, welche ein Werk Bestzeiten. Sie werden nicht (außer dem mit der Umsetzung Sie verwenden) müssen fast alles, was in den Rest des Codes geändert werden.

Die Schnittstelle für einen Baum und eine Hash-Tabelle (die ich bin zu raten ist, was Ihr Wörterbuch one basiert) soll sehr ähnlich sein. Immer rund um verkeilt Lookups.

hatte ich immer gedacht, ein Wörterbuch besser war für die Erstellung Dinge einmal und dann dann viele Lookups auf es zu tun. Während ein Baum besser war, wenn man es deutlich wurde modifiziert. Aber ich weiß nicht, wo ich diese Idee aufgegriffen aus.

(Funktionale Sprachen verwenden oft Bäume als Grundlage für sie Sammlungen, wie Sie wiederverwenden können die meisten des Baumes, wenn Sie kleine Änderungen zu machen).

Du vergleichst nicht „Äpfel mit Äpfeln“, ein BST gibt Ihnen eine bestellt Darstellung, während ein Wörterbuch ermöglicht es Ihnen, einen Lookup auf einem Schlüsselwertpaar zu tun (in Ihrem Fall).

Ich würde nicht viel Größe in der Speicherbedarf erwarten zwischen 2, aber das Wörterbuch gibt Ihnen eine viel schnellere Lookup. Um ein Element in einem BST Sie (potenziell) Notwendigkeit zu finden den gesamten Baum zu durchqueren. Aber eine dictnary Lookup zu tun Lookup Sie einfach basierend auf dem Schlüssel.

Eine ausgewogene BST ist vorzuziehen, wenn Sie Ihre Datenstruktur aus der Latenz Spikes und Hash-Kollisionen Angriffen schützen müssen.

Erstere tritt auf, wenn ein Array-backed-Struktur wächst eine Größe verändert wird, wobei die letztere ist eine unvermeidliche Eigenschaft des Algorithmus als Projektion von unendlichen Raum bis zu einem begrenzten ganzzahligen Bereich Hashing.

Ein weiteres Problem in .NET ist, dass es LOH ist, und mit einem ausreichend großen Wörterbuch laufen Sie in eine LOH Fragmentierung. In diesem Fall können Sie einen BST verwenden, einen Preis von größerer algorithmischer Komplexität der Klasse.

Kurz gesagt, mit einem BST durch die Zuordnung gesichert Heap Sie schlimmsten Fall O erhalten (log (N)) Zeit, mit hashtable Sie O (N) worst case Zeit.

BST kommt zu einem Preis von O (log (N)) durchschnittliche Zeit, schlechter Cache-Lokalität und mehr Heapzuweisungen, aber es hat Latenz garantiert und wird von Wörterbuch-Attacken und Speicherfragmentierung geschützt.

Bemerkenswert, dass BST ist auch ein Thema zu Speicherfragmentierung auf anderen Plattformen, keine Verdichtungs Garbage Collector verwendet wird.

Wie für die Speichergröße ist die .NET Dictionary`2 Klasse mehr Speicher effizient, weil es Daten als Off-Heap verknüpften Liste speichert, die nur speichert Wert und Offset-Informationen. BST hat zum Speichern von Objekt-Header (wie jeder Knoten eine Klasseninstanz auf dem Heap ist), zwei Zeiger, und einige Augmented Baumdaten für ausgeglichene Bäume. Zum Beispiel müßte ein rot-schwarz-Baum einen boolean interpretiert als Farbe (rot oder schwarz). Dies ist zumindest 6 Maschine Worten, wenn ich mich nicht irre. So kann jeder Knoten in einem rot-schwarz-Baum auf 64-Bit-System ist ein Minimum von:

3 Worte für den Header = 24 Bytes 2 Wörter für die untergeordneten Zeiger = 16 Bytes 1 Wort für die Farbe = 8 Bytes mindestens 1 Wort für den Wert 8+ bytes = 16 + 24 + 8 + 8 = 56 Bytes (8 Bytes, wenn der Baum einen übergeordneten Knoten Zeiger verwendet).

Zur gleichen Zeit, die Mindestgröße des Wörterbucheintrags würde nur 16 Byte sein.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top