In die verschiedenen Prolog-Programme wurden Befehle eingebaut, die Informationen über die
verbrauchte Prozessor-Zeit und die Größe des lokalen, globalen, Variablen- und Constraint-Stacks
ausgab, wobei run
einen Baum erstellt, layoutet und für das Perl-Skript formatiert ausgibt.
stat :- run, statistics(real_time, [RealTimeSinceStart, _]), statistics(local_stack, [LocalStack, _]), statistics(global_stack, [GlobalStack, _]), statistics(trail_stack, [TrailStack, _]), statistics(cstr_stack, [ConstraintStack, _]), print('Stat: time since startup in milliseconds: '), print(RealTimeSinceStart), nl, print('Stat: local stack in bytes: '), print(LocalStack), nl, print('Stat: global stack in bytes: '), print(GlobalStack), nl, print('Stat: trail stack (vars to be freed) in bytes: '), print(TrailStack), nl, print('Stat: constraint stack in bytes: '), print(ConstraintStack), nl, halt.
*** trees with simple tree *** time since startup in milliseconds: 56 local stack in bytes: 4148 global stack in bytes: 3164 trail stack (vars to be freed) in bytes: 6640 constraint stack in bytes: 5344 *** trees with tree with 5 levels*** time since startup in milliseconds: 265 local stack in bytes: 51240 global stack in bytes: 35568 trail stack (vars to be freed) in bytes: 390964 constraint stack in bytes: 95716
*** trees2 with simple tree *** time since startup in milliseconds: 66 local stack in bytes: 2492 global stack in bytes: 3388 trail stack (vars to be freed) in bytes: 5096 constraint stack in bytes: 5344 *** trees2 with tree with 5 levels*** time since startup in milliseconds: 113 local stack in bytes: 2492 global stack in bytes: 3388 trail stack (vars to be freed) in bytes: 5096 constraint stack in bytes: 5344
*** bb_tree with simple tree *** time since startup in milliseconds: 431 local stack in bytes: 1452 global stack in bytes: 3568 trail stack (vars to be freed) in bytes: 4680 constraint stack in bytes: 5308 *** bb_tree with tree with 5 levels*** time since startup in milliseconds: 270687 local stack in bytes: 21452 global stack in bytes: 39680 trail stack (vars to be freed) in bytes: 114480 constraint stack in bytes: 96444
*** bb_tree2 with simple tree *** time since startup in milliseconds: 196 local stack in bytes: 864 global stack in bytes: 1928 trail stack (vars to be freed) in bytes: 1832 constraint stack in bytes: 2420 *** bb_tree2 with tree with 5 levels*** time since startup in milliseconds: 415386 local stack in bytes: 21952 global stack in bytes: 49448 trail stack (vars to be freed) in bytes: 133264 constraint stack in bytes: 116996
Die Statistiken für den einfachen Baum sind eher zu vernachlässigen, da dieser Baum zu klein ist, um die Unterschiede der Algorithmen wirklich aufzuzeigen. Der Baum mit 5 Ebenen und 64 Knoten kann eher als Vergleichsgrundlage dienen.
Bei dem Original-Algorithmus schlägt sich die Ersparnis von mehreren Baumdurchgängen in der Zeit und im Speicherverbrauch sofort nieder. Seltsam ist, daß sich die Constraint-Stacks so unterscheiden, obwohl die Constraint-Bedingungen die gleichen sind.
Beim Bounding Box-Algorithmus verwundert es mich, daß die Version mit weniger Baumdurchgängen teilweise doppelt so schlecht wie die einfache ist. Auch hier kann ich mir die Unterschiede beim Constraint-Stack nicht erklären.
Die Bounding Box-Varianten brauchen mehr Constraint-Variablen, weil sie auch mehr Constraints haben: die Koordinaten der beiden Ecken und die x-Koordinate der Wurzel werden berechnet, wobei der Original-Algorithmus nur die Koordinaten jedes Knotens berechnet. Deshalb sind die Bounding Box-Algorithmen auch langsamer als die Original-Version.