Vergleich von Suchverfahren mit Beispielen

[alzaimar]

Der B-Baum ist eine Mischung aus T-ärem Baum und Binary Search, wird also in der Performance irgendwo dazwischen sein.
Desweiteren ist der BB für Daten gedacht, die sich auf einem externen Datenträger befinden, und passt deshalb vom Konzept her hier nicht rein.

Ich vermute auch, das der Overhead etwas zu hoch ist, um mit reinen in-Memory-Lösungen mithalten zu können.

[Dezipaitor]

Die Suche/Einfügen/Löschen ist in einen B-Baum mit b-Einträge pro Knoten in schlechtesten Fall in O(b_log n) Schritten geschafft. Der B+ Baum hat sogar den Vorteil, dass nur die Blätter echte Daten enthalten und in einer linearen Liste verkettet sind, so dass eine Speicherung nur O(n) Speicherplatz braucht.

Dieses Video zeigt, wie ein B-Baum erstellt wird
http://youtube.com/watch?v=coRJrcIYbF4

Also warum sollte so ein Kunststück fehlen sollen?

[mschaefer]

Zitat:

Zitat von Dezipaitor

Also warum sollte so ein Kunststück fehlen sollen?

Ohne übermäßig zu Lästern würde ich es mal so beantworten: Weil Alzeimer vielleicht keine Zeit hat und Du es nicht umsetzen magst (kannst?).
Gib Ihm kein Viedeo sondern Deine Implementierung und er baut es bestimmt ein.
Aber ich gehe davon aus, dass er keine schnellere Variante sein wird (gerade in gut gecachten Rechnern).

Grüße // Martin

[alzaimar]

Zitat:

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.

[abrosda]

Ich werd' mal sehen, ob ich vor Weihnachten ein bischen Zeit an meinem Rechner zu Hause habe und dann noch ein paar Algorhithmen hinzufügen. Interessant ist ein Vergleich zwischen den Stringvergleichen und Integervergleichen...

[alzaimar]

Zitat:

Zitat von abrosda

Interessant ist ein Vergleich zwischen den Stringvergleichen und Integervergleichen...

Yo, gute Idee.

Vermutlich wird die Hashmap ggü. der Skiplist besser abschneiden, da bei der Hashmap (=Dictionary) der String per Hash-Funktion in einen Integer umgewandelt wird. Anschließend finden (fast) nur noch Integer-Vergleiche statt.

In allen anderen Strukturen wird dagegen der zu suchende Text stehts mit einem Schlüssel verglichen.

[mquadrat]

So, ich hab jetzt auch mal ein bisschen mit den Listen rumgespielt. Für den ein oder anderen vielleicht interessant: Wenn man bei der THashedStringlist die Sortierung weg lässt kann man für kleinere Datenmengen nochmal Geschwindigkeit rauskitzeln. Erst ab 50.000 Einträgen wird das Suchen extrem langsamer. Davor ist zwischen sortierten und unsortierten THashStringlists kaum ein Unterschied beim Suchen.

[alzaimar]

Das ist interessant! Hast Du deine Optimierung mal in die Teststruktur eingepflegt, sodaß man unmittelbar einen Vergleich mit den anderen Datenstrukturen ziehen kann?

Immer wieder wichtig ist zu wissen, ob und wie eine Datenstruktur skalierbar ist, ob sie also auch bei exorbitanten Datenmengen noch performant ist. Wenn man es braucht.

[Luckie]

@alzaimar: Wenn du alles zusammen hast, mach doch daraus ein Tutorial und poste es in der Tutorialsparte.

[Oreaden]

@Luckie: Feine Idee ein Tutorial zum Thema, wie erstelle ich eine Testumgebung

Hab da noch nichts gefunden und meine Kristallkugel läßt mich zu diesem Thema auch in Stich :roll:

Schöne Grüße
OREADEN