webentwicklung-frage-antwort-db.com.de

Binäre Bäume vs. Verknüpfte Listen vs. Hash-Tabellen

Ich erstelle eine Symboltabelle für ein Projekt, an dem ich arbeite. Ich habe mich gefragt, welche Meinungen die Leute zu den Vor- und Nachteilen der verschiedenen Methoden zum Speichern und Erstellen einer Symboltabelle haben.

Ich habe einiges gesucht und die am häufigsten empfohlenen sind Binärbäume, verknüpfte Listen oder Hash-Tabellen. Was sind die Vor- und Nachteile aller oben genannten? (arbeiten in c ++)

72
benofsky

Ihr Anwendungsfall wird vermutlich darin bestehen, "die Daten einmal einzufügen (z. B. Anwendungsstart) und dann viele Lesevorgänge durchzuführen, jedoch nur wenige, wenn überhaupt, zusätzliche Einfügungen".

Daher müssen Sie einen Algorithmus verwenden, mit dem Sie schnell die benötigten Informationen abrufen können.

Ich denke daher, dass HashTable der am besten geeignete Algorithmus ist, da es einfach einen Hash Ihres Schlüsselobjekts generiert und diesen verwendet, um auf die Zieldaten zuzugreifen - es ist O (1). Die anderen sind O(N) (Verknüpfte Listen der Größe N - Sie müssen die Liste einzeln durchlaufen, durchschnittlich N/2 Mal) und O (log N) ( Binärer Baum - Sie halbieren den Suchraum mit jeder Iteration - nur wenn der Baum ausgeglichen ist. Dies hängt also von Ihrer Implementierung ab. Ein unausgeglichener Baum kann eine erheblich schlechtere Leistung haben.

Stellen Sie einfach sicher, dass in der HashTable genügend Speicherplätze (Eimer) für Ihre Daten vorhanden sind (siehe Soraz 'Kommentar zu diesem Beitrag). Die meisten Framework-Implementierungen (Java, .NET usw.) weisen eine Qualität auf, die Sie bei den Implementierungen nicht beachten müssen.

Haben Sie an der Universität einen Kurs über Datenstrukturen und Algorithmen gemacht?

48
JeeBee

Es gelten die üblichen Kompromisse zwischen diesen Datenstrukturen.

  • Binäre Bäume
    • mittlere Komplexität bei der Implementierung (vorausgesetzt, Sie können sie nicht aus einer Bibliothek abrufen)
    • einsätze sind O (logN)
    • lookups sind O (logN)
  • 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
    • beilagen sind im Durchschnitt O(1)
    • lookups sind im Durchschnitt O(1)
74
Darron

Was jeder zu vergessen scheint, ist, dass für kleine Ns, IE wenige Symbole in Ihrer Tabelle, die verknüpfte Liste viel schneller sein kann als die Hash-Tabelle, obwohl theoretisch ihre asymptotische Komplexität in der Tat höher ist.

Es gibt eine berühmte Qoute aus Pikes Anmerkungen zur Programmierung in C: "Regel 3. Phantasie-Algorithmen sind langsam, wenn n klein ist, und n ist normalerweise klein. Phantasie-Algorithmen haben große Konstanten. Bis Sie wissen, dass n häufig groß sein wird, bekomme keine Lust. " http://www.lysator.liu.se/c/pikestyle.html

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

42

Es hört sich so an, als ob alles wahr wäre:

  • Ihre Schlüssel sind Zeichenfolgen.
  • Einfügungen werden einmal durchgeführt.
  • Suchen werden häufig durchgeführt.
  • Die Anzahl der Schlüssel-Wert-Paare ist relativ gering (beispielsweise weniger als ein K oder so).

In diesem Fall können Sie eine sortierte Liste für eine dieser anderen Strukturen in Betracht ziehen. Dies würde beim Einfügen schlechter abschneiden als bei den anderen, da eine sortierte Liste O(N) beim Einfügen im Vergleich zu O(1) für eine verknüpfte Liste oder Hash-Tabelle und O (log2N) für einen ausgeglichenen Binärbaum. Suchvorgänge in einer sortierten Liste sind jedoch möglicherweise schneller als alle anderen Strukturen (ich werde dies in Kürze erläutern), sodass Sie möglicherweise die Nase vorn haben. Wenn Sie alle Einfügungen gleichzeitig ausführen (oder ansonsten keine Suche benötigen, bis alle Einfügungen abgeschlossen sind), können Sie die Einfügungen zu O(1) vereinfachen und eine wesentlich schnellere Sortierung durchführen Außerdem benötigt eine sortierte Liste weniger Speicher als jede dieser anderen Strukturen, aber dies ist wahrscheinlich nur dann von Bedeutung, wenn Sie viele kleine Listen haben. Wenn Sie eine oder mehrere große Listen haben, dann ein Hash Tabelle wird wahrscheinlich eine sortierte Liste übertreffen.

Warum sind Suchvorgänge mit einer sortierten Liste möglicherweise schneller? Nun, es ist klar, dass es schneller als eine verknüpfte Liste ist, mit der O(N) Nachschlagezeit. Bei einem binären Baum bleiben Nachschlagezeiten nur O (log)2 N) wenn der Baum perfekt ausbalanciert bleibt. Wenn Sie den Baum im Gleichgewicht halten (z. B. rot-schwarz), erhöht sich die Komplexität und die Einfügezeit. Bei verknüpften Listen und Binärbäumen wird jedes Element separat zugewiesen1  Knoten , was bedeutet, dass Sie Zeiger dereferenzieren und wahrscheinlich zu potenziell stark variierenden Speicheradressen springen müssen, was die Wahrscheinlichkeit eines Cache-Miss erhöht.

In Bezug auf Hash-Tabellen sollten Sie wahrscheinlich ein paar von andere Fragen hier auf StackOverflow lesen, aber die wichtigsten Punkte, die hier von Interesse sind, sind:

  • Eine Hash-Tabelle kann im schlimmsten Fall zu O(N) degenerieren.
  • Die Kosten für das Hashing sind ungleich Null und können in einigen Implementierungen erheblich sein, insbesondere im Fall von Zeichenfolgen.
  • Wie in verknüpften Listen und Binärbäumen ist jeder Eintrag ein Knoten , der mehr als nur Schlüssel und Wert speichert und in einigen Implementierungen auch separat zugewiesen wird Mehr Speicher und höhere Wahrscheinlichkeit eines Cache-Ausfalls.

Wenn Sie sich wirklich für die Leistung dieser Datenstrukturen interessieren, sollten Sie sie natürlich testen. Sie sollten keine Probleme damit haben, eine gute Implementierung für die gängigsten Sprachen zu finden. Es sollte nicht allzu schwierig sein, einige Ihrer realen Daten in jede dieser Datenstrukturen zu werfen und festzustellen, welche Daten die beste Leistung bringen.

  1. Es ist für eine Implementierung möglich, ein Array von Knoten vorab zuzuweisen, was beim Cache-Miss-Problem helfen würde. Ich habe dies in keiner realen Implementierung von verknüpften Listen oder Binärbäumen gesehen (natürlich nicht in jeder), obwohl Sie sicherlich Ihre eigenen rollen könnten. Die Wahrscheinlichkeit eines Cache-Ausfalls ist jedoch immer noch etwas höher, da die Knotenobjekte notwendigerweise größer als die Schlüssel/Wert-Paare sind.
8
P Daddy

Ich mag Bills Antwort, aber sie fasst die Dinge nicht wirklich zusammen.

Aus den drei Möglichkeiten:

Verknüpfte Listen sind relativ langsam, um Elemente von (O (n)) zu suchen. Wenn Sie also eine Menge Anzahl von Elementen in Ihrer Tabelle haben oder viele Suchvorgänge durchführen, sind diese nicht die beste Wahl. Sie sind jedoch leicht zu bauen und auch leicht zu schreiben. Wenn die Tabelle klein ist und/oder Sie nach dem Erstellen immer nur einen kleinen Scan durchführen, ist dies möglicherweise die richtige Wahl.

Hash-Tabellen können unglaublich schnell sein. Damit dies jedoch funktioniert, müssen Sie einen guten Hash für Ihre Eingabe auswählen und einen Tisch auswählen, der groß genug ist, um alles ohne viele Hash-Kollisionen aufzunehmen. Das bedeutet, dass Sie etwas über die Größe und Menge Ihrer Eingabe wissen müssen. Wenn Sie dies vermasseln, erhalten Sie einen wirklich teuren und komplexen Satz verknüpfter Listen. Ich würde sagen, wenn Sie nicht im Voraus wissen, wie groß der Tisch sein wird, sollten Sie keinen Hash-Tisch verwenden. Dies stimmt nicht mit Ihrer "akzeptierten" Antwort überein. Es tut uns leid.

Das lässt Bäume. Sie haben hier jedoch die Möglichkeit: auszugleichen oder nicht auszugleichen. Ich habe bei der Untersuchung dieses Problems mit C- und Fortran-Code festgestellt, dass die Symboltabelleneingabe in der Regel so zufällig ist, dass Sie nur ein oder zwei Baumebenen verlieren, wenn Sie den Baum nicht ausgleichen. Angesichts der Tatsache, dass ausgeglichene Bäume langsamer in Elemente eingefügt und schwerer zu implementieren sind, würde ich mich nicht mit ihnen befassen. Wenn Sie jedoch bereits Zugriff auf die in Nice debuggten Komponentenbibliotheken haben (z. B. die STL von C++), können Sie auch den ausgeglichenen Baum verwenden.

7
T.E.D.

Ein paar Dinge, auf die Sie achten sollten.

  • Binäre Bäume haben nur O (log n) Nachschlagen und Komplexität einfügen, wenn der Baum ausgeglichen ist . Wenn Ihre Symbole auf ziemlich zufällige Weise eingefügt werden, sollte dies kein Problem sein. Wenn sie der Reihe nach eingefügt werden, erstellen Sie eine verknüpfte Liste. (Für Ihre spezifische Anwendung sollten sie nicht in irgendeiner Reihenfolge vorliegen, daher sollten Sie in Ordnung sein.) Wenn die Wahrscheinlichkeit besteht, dass die Symbole zu geordnet sind, ist ein Rot-Schwarz Baum besser Möglichkeit.

  • Hash-Tabellen geben O(1) die durchschnittliche Komplexität beim Einfügen und Nachschlagen an, aber es gibt auch hier eine Einschränkung. Wenn Ihre Hash-Funktion schlecht ist (und ich meine wirklich) schlecht) Sie könnten auch hier eine verknüpfte Liste erstellen. Jede sinnvolle String-Hash-Funktion sollte dies jedoch tun, sodass diese Warnung nur dazu dient, um sicherzustellen, dass Sie sich dessen bewusst sind, dass dies passieren könnte Sie sollten nur testen können, ob Ihre Hash-Funktion über den erwarteten Eingabebereich nicht viele Kollisionen aufweist, und es wird Ihnen nichts ausmachen. Ein weiterer kleiner Nachteil ist die Verwendung einer Hash-Tabelle mit fester Größe Hash-Tabellen-Implementierungen nehmen zu, wenn sie eine bestimmte Größe erreichen (genauer gesagt, Ladefaktor, siehe hier für Details). Dies soll das Problem vermeiden, das beim Einfügen von einer Million Symbolen in zehn Buckets auftritt Das führt nur zu zehn verknüpften Listen mit einer durchschnittlichen Größe von 100.000.

  • Ich würde eine verknüpfte Liste nur verwenden, wenn ich eine wirklich kurze Symboltabelle hätte. Es ist am einfachsten zu implementieren, aber die beste Fallleistung für eine verknüpfte Liste ist die schlechteste Fallleistung für Ihre anderen beiden Optionen.

6
Bill the Lizard

Andere Kommentare haben sich auf das Hinzufügen/Abrufen von Elementen konzentriert, aber diese Diskussion ist nicht vollständig, ohne zu überlegen, was erforderlich ist, um die gesamte Sammlung zu durchlaufen. Die kurze Antwort hier ist, dass Hash-Tabellen weniger Speicher zum Durchlaufen benötigen, Bäume jedoch weniger Zeit.

Bei einer Hash-Tabelle hängt der Speicheraufwand für die Iteration über die (Schlüssel-, Wert-) Paare nicht von der Kapazität der Tabelle oder der Anzahl der in der Tabelle gespeicherten Elemente ab. Tatsächlich sollte das Iterieren nur eine oder zwei einzelne Indexvariablen erfordern.

Bei Bäumen hängt der Speicherbedarf immer von der Größe des Baums ab. Sie können entweder eine Warteschlange mit nicht besuchten Knoten verwalten, während Sie iterieren, oder dem Baum zusätzliche Zeiger hinzufügen, um die Iteration zu vereinfachen (damit der Baum für Iterationszwecke wie eine verknüpfte Liste funktioniert). In beiden Fällen müssen Sie jedoch zusätzlichen Speicher für die Iteration zuweisen .

Beim Timing ist die Situation jedoch umgekehrt. Bei einer Hash-Tabelle hängt die Zeit für die Iteration von der Kapazität der Tabelle und nicht von der Anzahl der gespeicherten Elemente ab. Eine mit 10% der Kapazität geladene Tabelle benötigt also etwa 10-mal länger als eine verknüpfte Liste mit denselben Elementen!

1
anonymous

Das hängt natürlich von mehreren Dingen ab. Ich würde sagen, dass eine verknüpfte Liste keine Rolle spielt, da sie nur wenige geeignete Eigenschaften hat, um als Symboltabelle zu arbeiten. Ein binärer Baum könnte funktionieren, wenn Sie bereits einen haben und keine Zeit damit verbringen müssen, ihn zu schreiben und zu debuggen. Meine Wahl wäre eine Hash-Tabelle, ich denke, das ist mehr oder weniger die Standardeinstellung für diesen Zweck.

0
unwind

Diese Frage durchläuft die verschiedenen Container in C #, sie sind jedoch in jeder von Ihnen verwendeten Sprache ähnlich.

0

Sofern Sie nicht erwarten, dass Ihre Symboltabelle klein ist, sollte ich mich von verknüpften Listen fernhalten. Eine Liste mit 1000 Elementen benötigt im Durchschnitt 500 Iterationen, um ein Element darin zu finden.

Ein binärer Baum kann viel schneller sein, solange er ausgeglichen ist. Wenn Sie den Inhalt beibehalten, wird das serialisierte Formular wahrscheinlich sortiert, und wenn es erneut geladen wird, ist der resultierende Baum infolgedessen völlig unausgeglichen und verhält sich genauso wie die verknüpfte Liste - weil das so ist im grunde was es geworden ist. Ausgewogene Baumalgorithmen lösen dieses Problem, machen den gesamten Shebang jedoch komplexer.

Eine Hashmap (solange Sie einen geeigneten Hashalgorithmus auswählen) scheint die beste Lösung zu sein. Sie haben Ihre Umgebung nicht erwähnt, aber in fast allen modernen Sprachen ist eine Hashmap integriert.

0
Martin Cowie