Unterabschnitte

Statistiken der verschiedenen Algorithmen

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.

Abbildung 1: Einfacher Baum
\includegraphics[angle=0,width=13cm]{s_tree.eps}

Abbildung 2: Baum mit 5 Ebenen
\includegraphics[angle=0,width=13cm]{l_tree.eps}

Dann wurde ein Shell-Skript erstellt, das für einen einfachen Baum und einen Baum mit 5 Ebenen diese Ergebnisse von 3 Versionen des Original-Algorithmus und 2 Versionen des Bounding-Box-Programms in eine Datei schrieb. Das Ergebnis war etwas verblüffend, da die Bounding-Box-Versionen fast immer mehr Speicher und Zeit brachten als die Ebenen-Versionen. Auch bei diesen war das Vermeiden von extra Baumdurchgängen kaum zu bemerken, die Original-Version ist sogar besser als die dritte!

Die Ergebnisse des Original-Algorithmus mit einfachem Perl-Skript (ohne Äste)

*** 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

Die Ergebnisse des verbesserten Algorithmus mit verbessertem Perl-Skript (mit Ästen)

*** 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

Die Ergebnisse des ersten Bounding Box-Algorithmus mit einfachem Perl-Skript

*** 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

Die Ergebnisse des zweiten Bounding Box-Algorithmus mit verbessertem Perl-Skript

*** 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.