>>164192A
ffenbrot-Baum meldet sich, Felix antwortet! :)
>Aber eigentlich sind B-Bäume bzw. B+-Bäume doch gerade "Wir machen das mit dem Array"
Ja, aber eben mit den Arrays in einem Baum angeordnet, und man muss sich immer noch zu den Array hinhangeln.
>Man will die Knoten so breit wie möglich haben, weil dann die Höhe des Baumes umso niedriger ist. In der Regel hat man dann nur ein, zwei oder maximal drei Level.
Ja!
Ohne Blöcke wie beim B-Baum sollte man Felixens Meinung nach Bäume heutzutage gar nicht erst versuchen.
>Bäume betrachte ich hingegen eher als ständig sortierte Arrays
>Bereichsanfragen
Wenn man "ständige Sortierung" oder "Bereichsabfragen" will, dann sollte man nicht Hash-Tabellen verwenden! Nicht umsonst gibt es in der besondersten Programmiersprache der Welt die Unterscheidung zwischen
std::unordered_map und
std::map. Und wie zu erwarten, sind die Namen genau unpraktisch gewählt (es wäre
std::map und
std::ordered_map besser gewesen) und aufgrund eines Spezifikationsfehlers im Standard kann man
std::unordered_map nicht mit offener Adressierung implementieren. Mit dem Gegenangriff
std::flat_map wird das alles bestimmt in Ordnung kommen.
Aber gerade bei Bereichsabfragen ist das nicht zu verwenden, und z.B. die Computergrafik hat ihre eigenen BVH-Datenstrukturen (wobei die auch ihr "spatial hashing" für Lookups entdeckt haben).
>drüberiterieren
Wenn man über _alle_ Einträge einer Hash-Tabelle (also nicht nur in einem Bereich) drüber iterieren will, sollte die Hash-Tabelle eine Zugriffsmöglichkeit bieten, mit der man über das dahinterliegende Daten-Array iterieren kann. Dann muss man aber leere/ge-Grabstein-te Elemente überspringen. Hash-Tabellen haben in der Regel einen Maximalfüllstand (z.B. 80 %) und entsprechenden Minimalfüllstand (z.B. 20 %). Demenstprechend kann man tatsächlich bis zum 80 % leere Elemente haben, wo der Zugriff vergeudet ist.
Das gilt jedoch nicht bei "stabilen" Hash-Tabellen, welche ein nochmals dahinterliegendes Daten-Array haben, welches dicht gepackt ist, auf welches das Key-Value-Array zeigt. Das Daten-Array kann höchstens bei Löschungen Einträge wie bei einer Free-List haben, die überspringen werden müssen, aber beim Hinzufügen wieder gefüllt werden. Das ist in der Regel damit sehr kompakt beim Durchiterieren über alle Elemente, ohne vergeudete Zugriffe.
>Ropes
Felix präferiert Piece-Tables. :)
>Bäume haben vielleicht einen schlechten Ruf wegen Rot-Schwarz-Bäumen und AVL-Bäumen: Dort hat jeder Knoten immer nur maximal zwei Kinder, weshalb der Baum sehr tief ist. Und die Knoten sind dann auch noch quer über den Heap vertreut. Das ist natürlich ineffizient.
Warum lernt man die eigentlich als Paradebeispiel für Bäume in der Uni?
>Weiterer Nachteil der Hashtabelle (und auch Skipliste): Sie sind probabilistisch, während balancierte Bäume vollkommen deterministisch sind.
Skiplisten werden klassischerweise mit PRNG implementiert, Felix hat sie mit Hashfunktion implementiert.
Hash-Tabellen und Skiplisten sind beide deterministisch, aber beide können mit pseudo-randomisierter Hashfunktion implementiert werden, indem man einen Seed XOR't.
Ich glaube, Abseil macht das.
Wobei die von Google diesbezüglich einen großkotzigen Blockpfosten rausgehauen haben, dass die KI (die KI!!) ihnen nun eine bessere Hashfunktion geliefert habe, die ja besonders super toll sei, und sie diese Hashfunktion nun in Abseil implementiert haben. Plotttwist: Die Leute von Google haben diese angeblich bessere Hashfunktion dann nach 2 Jahren wieder aus der Kotbasis rausgeworfen, und essentiell durch das gute, alte Knuth-Hashing plus Seed ersetzt. Natürlich still und heimlich, ein "Hupsi, hab gefeeft" macht sich schließlich nicht gut in einem Blockpfosten.
>Bäume sind eigentlich schon ganz kühl
>Man kann sie eigentlich für alles ohne Bedenken nehmen, es gibt keine pathologischen Fälle.
Man kann aufsteigende Werte einfügen, bis jeder Knoten im B-Baum fast ganz gefüllt ist, und dann beim nächsten Einfügen eine Kettenreaktion auslösen?
Ebenso beim Löschen, wenn jeder Knoten im B-Baum ganz knapp über dem Minimum liegt.
Das klappt natürlich bei Rot-Schwarz-Bäumen und AVL-Bäumen ganz besonders gut, weil dort Minimum und Maximum zusammenfallen.
>It just works.
Wenn man sich mit Zeigerjagt abgibt. Zugegebenermaßen gibt es in den meisten Kotbasen ganz andere Probleme als die Zeigerjagt.
Felix hat jedoch im Profiling bereits auffällig häufig
std::ordered_map oben gesehen.