Binary Trees vs. Linked Lists vs. Hash Tables

https://stackoverflow.com/questions/371136

21-08-2019
|

Frage

Ich baue eine Symboltabelle für ein Projekt arbeite ich an. Ich frage mich, was Völker Meinungen über die Vorteile und Nachteile der verschiedenen Methoden zur Speicherung und eine Symboltabelle zu erstellen.

Ich habe ein gutes Stück der Suche gemacht und die am häufigsten empfohlen sind Binärbäumen oder verkettete Listen oder Hash-Tabellen. Was sind die Vor- und Nachteile oder aller der oben genannten? (Arbeits in C ++)

Lösung

Ihr Anwendungsfall wird vermutlich sein werde „sobald die Daten einfügen (zum Beispiel Start der Anwendung) und führen Sie dann viel liest, aber nur wenige, wenn irgendwelche zusätzliche Einfügungen“.

Sie benötigen daher einen Algorithmus verwenden, die zum Nachschlagen der Informationen schnell, die Sie benötigen.

Ich würde denken, damit die HashTable der am besten geeignete Algorithmus zu verwenden ist, da es einfach ist, einen Hash des Schlüsselobjekts zu erzeugen und dass die Zieldaten für den Zugriff auf mit - es ist O (1). Die anderen sind O (N) (verketteten Listen der Größe N - Sie durch die Liste einer nach dem anderen zu durchlaufen haben, einen Durchschnitt von N / 2 mal) und O (log N) (Binary Tree - halbieren Sie den Suchraum mit jede Iteration -. nur dann, wenn der Baum ausgeglichen ist, so hängt dies von den jeweiligen Implementierung, ein unausgewogener Baum deutlich schlechtere Leistung hat)

nur sicherstellen, dass es genügend Plätze (Eimer) in der HashTable sind für Ihre Daten (R. E., Soraz Kommentar zu diesem Beitrag). Die meisten Framework-Implementierungen (Java, .NET, etc.) von einer Qualität sein, die Sie nicht über die Implementierungen kümmern müssen.

Hast du einen Kurs über Datenstrukturen und Algorithmen an der Universität?

Andere Tipps

Die Standard-Abwägungen zwischen diesen Datenstrukturen anzuwenden.

Binary Trees
- mittlere Komplexität zu implementieren (vorausgesetzt, Sie sie nicht aus einer Bibliothek bekommen)
- Einsätze sind O (log N)
- Lookups sind O (log N)
Verknüpfte Listen (unsortiert)
- geringe Komplexität zu implementieren
- Einsätze sind O (1)
- Lookups sind O (N)
Hash-Tabellen
- hohe Komplexität zu implementieren
- Einsätze sind O (1) im Durchschnitt
- Lookups ist O (1) im Durchschnitt

Was jeder scheint zu vergessen ist, dass für kleinen Ns, IE einige Symbole in der Tabelle können die verknüpfte Liste viel schneller sein als die Hash-Tabelle, obwohl in der Theorie seine asymptotische Komplexität ist in der Tat höher.

Es gibt eine berühmte qoute von Pikes Hinweise zur Programmierung in C: „. Regel 3. Fancy Algorithmen sind langsam, wenn n klein ist, und n ist in der Regel klein Fancy Algorithmen große Konstanten haben, bis Sie wissen, dass n häufig geht zu. groß sein, nicht Lust bekommen.“ http://www.lysator.liu.se/c/pikestyle.html

Ich kann nicht von Ihrem Beitrag sagen, wenn Sie mit einem kleinen N oder nicht tun wird, aber immer daran denken, dass der beste Algorithmus für große N ist nicht unbedingt gut für kleine Ns.

Es klingt wie die folgenden wahr sein:

Ihre Schlüssel sind Strings.
Einsätze werden einmal getan.
Lookups fertig sind häufig.
Die Anzahl der Schlüssel-Wert-Paare relativ klein ist (sagen wir, weniger als ein K oder so).

Wenn ja, könnten Sie eine sortierte Liste über alle diese anderen Strukturen berücksichtigen. Dies würde schlechter abschneiden als die anderen bei Einsätzen, als eine sortierte Liste O (N) auf dem Einsatz ist, im Vergleich zu O (1) für eine verknüpfte Liste oder Hash-Tabelle, und O (log ₂ N) für ein ausgewogener binärer Baum. Aber Lookups in einer sortierten Liste kann schneller sein als alle diese anderen Strukturen (Ich werde dies kurz erklären), so dass Sie kommen an die Spitze kann. Auch, wenn Sie auf einmal alle Ihre Einsätze durchführen (oder auf andere Weise nicht Lookups erfordern, bis alle Einfügungen abgeschlossen sind), dann können Sie Einfügungen O vereinfachen (1) und führen Sie eine viel schnelle Art am Ende. Was mehr ist, verwendet eine sortierte Liste weniger Speicher als eine dieser anderen Strukturen, aber der einzige Weg, dies wahrscheinlich egal ist, wenn Sie viele kleine Listen haben. Wenn Sie ein oder ein paar großen Listen haben, dann eine Hash-Tabelle aus-führt eine sortierte Liste wahrscheinlich ist.

Warum könnte Lookups schneller mit einer sortierten Liste? Nun, es ist klar, dass es schneller als eine verknüpfte Liste, mit dessen O (N) Lookup-Zeit. Mit einem binären Baum, Lookups bleiben nur O (log ₂ N), wenn der Baum perfekt ausbalanciert bleibt. Halten Sie den Baum ausgeglichen (rot-schwarz, zum Beispiel) erhöht die Komplexität und Einführungszeit. Zusätzlich beide mit verknüpften Listen und Binärbäumen, ist jedes Element ein separat zugewiesen ¹ node , das bedeutet, dass Sie weit zu dereferenzieren Zeiger und wahrscheinlich Sprung zu potenziell haben werden variiert Speicheradressen, die Chancen für eine Cache-Miss zu erhöhen.

Wie bei Hash-Tabellen, sollten Sie wahrscheinlich lesen ein paar von weitere Fragen hier auf Stackoverflow, aber die wichtigsten Sehenswürdigkeiten sind hier:

Eine Hash-Tabelle zu O (N) im schlimmsten Fall degenerieren kann.
Die Kosten für Hashing nicht Null ist, und in einigen Implementierungen kann es von Bedeutung sein, insbesondere im Fall von Strings.
Wie in verkettete Listen und Binärbäumen, ist jeder Eintrag ein node mehr als nur Schlüssel und Wert zu speichern, auch in einigen Implementierungen separat zugewiesen, so dass Sie mehr Speicherplatz und die Chancen eines Cache erhöhen Miss.

Natürlich, wenn Sie sich wirklich interessieren, wie jeder dieser Datenstrukturen durchführen wird, sollten Sie sie testen. Sie sollten wenig Probleme zu finden, haben gute Implementierungen von jeder dieser für die meisten gängigen Sprachen. Es sollte nicht allzu schwierig sein, einige Ihrer realen Daten an jedem dieser Datenstrukturen zu werfen und sehen, welche die beste Leistung erzielt.

_{Es ist möglich, dass eine Implementierung eine Reihe von Knoten im Voraus zuweisen, die mit dem Cache-Miss-Problem helfen würden. Ich habe das nicht in irgendeiner realen Implementierung von verknüpften Listen oder Binärbäumen gesehen (nicht, dass ich jeden, natürlich gesehen), obwohl Sie sicherlich Ihre eigene Rolle könnten. Sie würden immer noch eine etwas höhere Wahrscheinlichkeit einer Cache-Miss haben, obwohl, da die node Objekte notwendigerweise größer als die Schlüssel / Wert-Paar sein würden.}

Ich mag Bills Antwort, aber es ist nicht wirklich Dinge synthetisieren.

Von den drei Möglichkeiten:

Verknüpfte Listen sind relativ langsame Elemente zum Nachschlagen von (O (n)). Also, wenn Sie ein Los von Elementen in der Tabelle, oder Sie werden eine Menge von Lookups zu tun, dann sind sie nicht die beste Wahl. Allerdings sind sie leicht zu bauen und einfach zu schreiben. Wenn die Tabelle klein ist, und / oder Sie immer nur durch sie eine kleine Scan tun, nachdem es gebaut wird, dann könnte dies die richtige Wahl für Sie sein.

Hash-Tabellen können unglaublich schnell sein. Doch für die es Sie zu arbeiten, haben eine gute Hash für Ihre Eingabe zu holen, und Sie müssen einen Tisch groß genug wählen, alles zu halten, ohne eine Menge von Hash-Kollisionen. Was das bedeutet, ist, dass Sie etwas über die Größe und Quantität Ihrer Eingabe kennen. Wenn Sie Schlamassel diese auf, am Ende mit einer wirklich teueren und komplexer Reihe von verknüpften Listen auf. Ich würde sagen, dass, wenn Sie im Voraus wissen, etwa wie groß der Tisch sein wird, nicht über eine Hash-Tabelle verwenden. Diese nicht einverstanden mit Ihrem „akzeptiert“ zu beantworten. Es tut uns Leid.

Das läßt Bäume. Sie haben die Möglichkeit, hier aber: Zum Ausgleich oder nicht ausgleichen. Was ich durch das Studium dieses Problems auf C und Fortran Code, den wir hier haben gefunden, dass die Symboltabelle Eingang ausreichend zufällig zu sein scheint, dass Sie nur über einen Baum Ebene verlieren oder zwei durch den Baum nicht ausgleicht. Da ausgeglichene Bäume langsamer sind Elemente in einfügen und sind schwieriger zu implementieren, würde ich nicht mit ihnen stören. Wenn Sie jedoch bereits Zugang zu schön ausgetestet Komponentenbibliotheken (zB: C ++ 's STL)., Dann könnte man genauso gut voran gehen und den ausgewogenen Baum verwenden

Ein paar Dinge zu achten gilt.

Binäre Bäume haben nur O (log n) Lookup und Komplexität einfügen, wenn der Baum ausgewogen . Wenn Ihre Symbole in einer ziemlich zufälligen Weise eingeführt werden, sollte dies kein Problem sein. Wenn sie eingesetzt, um sind, hast du eine verkettete Liste bauen. (Für Ihre spezifische Anwendung sollten sie nicht in jeder Art von Ordnung sein, so sollten Sie in Ordnung sein.) Wenn es eine Chance, dass die Symbole zu ordentlich sein werden, ein Red-Black Baum ist eine bessere Option.
Hash-Tabellen geben O (1) durchschnittliche Insert und Lookup-Komplexität, aber es gibt einen Nachteil auch hier. Wenn Ihre Hash-Funktion ist schlecht (und ich meine wirklich schlecht) Sie auch hier eine verkettete Liste könnte am Ende zu bauen. Jede vernünftige String-Hash-Funktion sollte tun, obwohl, so dass diese Warnung wirklich nur um sicherzustellen, dass Sie sich bewusst sind, dass es passieren könnte. Sie sollten in der Lage sein, nur um zu testen, ob Ihre Hash-Funktion nicht viele Kollisionen über die erwarteten Bereich der Eingänge hat, und Sie werden in Ordnung. Ein weiterer kleiner Nachteil ist, wenn Sie mit einer festen Größe Hash-Tabelle. Die meisten Hash-Tabelle Implementierungen wachsen, wenn sie eine bestimmte Größe (Lastfaktor erreichen genauer zu sein, finden Sie unter hier für weitere Details). Das ist das Problem, das Sie erhalten, zu vermeiden, wenn Sie eine Million Symbole in zehn Eimer sind einsetzen. Das gerade führt zu zehn verkettete Listen mit einer durchschnittlichen Größe von 100.000.
Ich würde nur eine verkettete Liste verwenden, wenn ich eine wirklich kurze Symboltabelle hatte. Es ist am einfachsten zu implementieren, aber der beste Fall Leistung für eine verkettete Liste ist der schlimmste Fall Leistung für Ihre anderen beiden Optionen.

Andere Kommentare haben sich auf das Hinzufügen / Abrufen Elemente konzentriert, aber diese Diskussion ist nicht vollständig ohne überlegen, was es braucht, die ganze Sammlung iterieren. Die kurze Antwort ist, dass Hash-Tabellen weniger Speicher benötigen überlaufen, aber Bäume benötigen weniger Zeit.

Für eine Hash-Tabelle, der Speicher-Overhead von Iterieren über den (Schlüssel, Wert) -Paare, hängt nicht von der Fähigkeit der Tabelle oder die Anzahl von Elementen in der Tabelle gespeichert ist; in der Tat sollen, Iterieren benötigen nur eine einzige Indexvariable oder zwei.

Für Bäume, die benötigte Speichermenge hängt immer von der Größe des Baumes. Sie können entweder eine Warteschlange von unvisited Knoten halten, während Iterieren oder zusätzliche Hinweise zur einfacheren Iteration zu dem Baum hinzufügen (was den Baum, für die Zwecke der Iteration, wirken wie eine verknüpfte Liste), aber so oder so, haben Sie für Iteration zusätzliche Speicher zuweisen .

Aber die Situation umgekehrt wird, wenn es um Timing kommt. Für eine Hash-Tabelle, ist es die Zeit hängt von der Kapazität der Tabelle, nicht die Anzahl der gespeicherten Elemente iterieren nimmt. So eine Tabelle mit 10% der Kapazität geladen dauert etwa 10-mal länger iterieren als eine verknüpfte Liste mit den gleichen Elementen!

Das hängt von verschiedenen Dingen, natürlich. Ich würde sagen, dass eine verknüpfte Liste rechts aus, da es wenige geeignete Eigenschaften hat als Symboltabelle zu arbeiten. Ein binärer Baum könnte funktionieren, wenn Sie bereits einen haben, und müssen keine Zeit aufwenden Schreiben und Debuggen es. Meine Wahl eine Hash-Tabelle wäre, denke ich, dass mehr oder weniger ist die Standardeinstellung für diesen Zweck.

Diese Frage durchläuft, aber sie sind ähnlich in jeder Sprache, die Sie verwenden.

Wenn Sie Ihre Symboltabelle erwarten, klein zu sein, soll ich klar von verknüpften Listen lenken. Eine Liste von 1000 Elementen wird im Durchschnitt 500 Iterationen, um jeden Punkt in ihn zu finden.

Ein Binärbaum kann viel schneller sein, so lange es ausgeglichen ist. Wenn Sie die Inhalte sind persistierende, wird die serialisierte Form wahrscheinlich sortiert werden, und wenn es neu geladen wird, wird der resultierende Baum als Folge völlig un-ausgewogen sein, und es wird das gleiche wie die verknüpfte Liste verhalten - denn das ist im Grunde, was es geworden ist. Balanced Baum Algorithmen, diese Angelegenheit lösen, sondern machen den ganzen Kram komplexer.

Ein hashmap (so lange, wie Sie einen geeigneten Hashing-Algorithmus wählen) sieht aus wie die beste Lösung. Sie haben nicht Ihre Umgebung erwähnt, sondern nur über alle modernen Sprachen haben eine HashMap eingebaut.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow