Zitat von
Dezipaitor:
Also warum sollte so ein Kunststück fehlen sollen?
Ich schrieb doch bereits, das das der Bayer-Baum nicht hier herein passt, da es sich nicht um eine generische Struktur bzw. Algorithmus zum schnellen Speichern von Assoziationen
in-Memory handelt. Der Bayer-Baum wurde doch vor allen Dingen für Page-
I/O entwickelt, daher die Seiten konstanter Größe.
Im Übrigen benötigt man doch kein Video, um einen Algorithmus zu verstehen. Ein gutes Buch reicht.
Wie wäre es, wenn Du, Dezipaitor, eine B*-Baum-Klasse implementierst und in den Testcode einpflegst? Ich behaupte immer noch, das der Overhead der Seitenverwaltung zu viel Performance klaut. Und gegen eine Hashmap, Skiplist oder einen Trie (DAWG) kommt der BB-Monolith eh nicht an. Natürlich lasse ich mich gerne eines Besseren belehren. Du kannst den Code von Julian Bucknall als Grundlage verwenden, er schwirrt in den Tiefen des WWW irgendwo herum.
Bei der Gelegenheit könnte man auch einen DAWG mit aufnehmen, nur frisst so eine Datenstruktur dermaßen viel Speicher, das sie den Test nicht besteht. Dafür wäre ein DAWG schneller als ne Hashmap.
Wie gesagt, es ging mir nicht um eine vollständige Liste von Listenstrukturen und deren Performancevergleich. Ich habe einen schnellen in-Memory-Cache für einen Interpreter benötigt, und da ging eben die Analyse los. Letztendlich bin ich bei der Hashmap hängengeblieben, aber nur deshalb, weil ich das Verfahren verstanden habe. Die Skiplist habe ich im Zusammenhang mit dem Sourcecode des MS
SQL-Servers kennengelernt und wollte nur mal wissen, was ist. die AVL Bäume kenne ich noch aus meiner Studienzeit und -na ja- binary search lernt man in der Schule.
@mkinzler: Ich hab hier irgendwo eine B-Tree-Klasse rumliegen, aber wozu soll ich die einbauen (s.o.)? Wer will, kann das gerne selbst machen. Ich hab doch nicht das Monopol auf die Testumgebung.