Im Rahmen der Algorithmik Vorlesung von Prof. Iwanwoski (FH Wedel) im SS 2014 habe ich als Übungsaufgabe einen ab-Baum in C++ implementiert und mit der Variante eines Kommilitonen verglichen. Gegenstand einer oberflächlichen Untersuchung war dabei weniger die Laufzeit der Implementierung selbst, sondern das Verhalten für verschiedene Werte von a und b.

Der (a,b)-Baum

Der ab-Baum ist einer der Standardansätze zur Lösung des Dictionary Problems. Er implementiert die Operationen insert(key, value), lookup(key) und delete(key) in Ο(log n). Meine Implementierung des Baums entstand an einem verlängerten Nachmittag und war als Vorbereitung auf die Klausur angedacht.

Im Rahmen der Vorlesung wurde, bis auf die Invariante a ≥ 2, b ≥ 2a-1 natürlich, auf sinnvolle Werte für a und b nicht vertieft eingegangen. Empirisch scheinen wohl 2-4 Bäume eine ganz gute Wahl zu sein und Datenbanksysteme nutzen natürlich B-Bäume, welche als eine Variante der (a,b)-Bäume mit recht großen Werten für b gesehen werden können.

Die Daten

Verglichen werden hier die Implementierungen von Timm Hoffmann (mit Python) und mir (mit C++). Wir haben für die Generierung von Testfällen Python Skripte erstellt, welche Daten in einem speziellen Format für eine kleine Analyseumgebung bereitstellen. Als einzig interessanter Testfall hat sich, wie allerdings schon vorher vermutet, der ungünstigste Fall einer bereits sortierten Eingabe herausgestellt. Wir haben daher in 10.000er Schritten, beginnend mit 10.000 Elementen, sortierte Daten in den Baum eingefügt.

Das Ergebnis

Die Y-Achse ist logarithmisch skaliert und die Daten bestätigen selbstverständlich das zu erwartende logarithmische Zeitverhalten. Auffällig ist natürlich zunächst, dass die Implementierung in C++ etwas mehr als eine ganze Größenordnung schneller ist. Im Laufe der Vorlesung wurde diskutiert, ob es optimale Werte für a und b geben kann. Praktisch werden hier immer wieder die Werte a=2 und b=4 genannt.

Diese Werte können wir für unser Testzenario nicht bestätigen. Für die Python Implementierung verhält sich der (2,10)-Baum besser, für die C++ Implementierung mal der (2,10)-Baum und mal der (2,20)-Baum.

Die Analyseumgebung

Um meine Laufzeiten mit denen meiner Kommilitonen vergleichen zu können haben wir uns auf eine einfache Sprache für die Testumgebung geeinigt. Die Sprache verwendet grundsätzlich Kommata als Trennzeichen und interpretiert den ersten Wert als Anweisung.

Der Einfachheit halber arbeitet die Sprache mit zwei globalen Variablen: Alle Anweisungen die sich auf einen Baum beziehen verwenden den gleichen, globalen Baum. Zur Zeitmessung existiert dann noch ein globaler Timer.

Folgende Anweisungen stehen zur Verfügung:

create,<a>,<b>

Erstellt einen neuen (a,b)-Baum als implizite globale Variable.

insert,<key>,<value>

Fügt den Wert <value> mit dem Schlüssel <key> in den impliziten globalen Baum ein. Sollte der Schlüsssel schon vorhanden sein, wird der Wert aktualisiert.

contains,<key>,True|False

Prüft ob zu dem Schlüssel <key> ein Wert hinterlegt ist. Diese Anweisung kann in etwa wie eine Assertion verwendet werden, im Fehlerfall wird eine Meldung auf stderr ausgegeben.

timer,start|print

start setzt den globalen Timer auf 0 und beginnt mit der Zeitmessung, print gibt den aktuellen Wert des Timers in ms aus.

echo,<value>

Gibt den Wert <value> auf <stdout> aus. Die Zeichenfolge "\n" kann als Zeilenumbruch verwendet werden. Die Anweisung selbst setzt keinen impliziten Zeilenumbruch, sollte die Ausgabe aber flushen.