Inhaltsverzeichnis
6.1.3. Eigentlichkeit begünstigende Faktoren
Inhaltsverzeichnis
6.1.3. Eigentlichkeit begünstigende Faktoren
Für die Laufzeitmessung wurde ausschließlich die Statistikfunktion herangezogen. Alle Laufzeiten wurden auf dem gleichen Rechner unter den gleichen Bedingungen gemessen: auf einem 200 MHz-PC mit Windows 98, wobei das Front-End im Vordergrund lief und keine Prozesse außer den zum Betriebssystem gehörigen aktiv waren. Letzteres ist deshalb besonders wichtig, weil das Front-End die MTen aus den in Abschnitt 5.2.2. genannten Gründen in einem niedrig priorisierten Thread durchsucht. Das bedeutet nämlich auch, dass der Zählvorgang durch fremde Programme erheblich verzögert wird - durch manche Anwendungen wie z.B. Microsoft Word selbst dann, wenn diese während des Zählens nur geöffnet sind, ohne dass damit gearbeitet wird.
Auf die Messung der Zeiten für MTen mit zehn und weniger Gliedern wurde verzichtet, da die Laufzeiten dort so kurz sind, dass algorithmischer Overhead und Zugriffe auf die Programmoberfläche - vor allem die Darstellung des Fortschrittsbalkens - die Laufzeit der interessanten Kernalgorithmen zu stark verfälschen.
Mittels des Front-Ends lässt sich eine große Anzahl an verschiedenen Statistiken aufstellen. Die Frage ist also, für welche davon eine Laufzeitmessung überhaupt interessant wäre. An dem Algorithmus zum Ermitteln der Statistik fällt dabei auf, dass - egal, nach welchen Kriterien die MTen eingeschränkt sind oder für welches Kriterium die Statistik aufgestellt werden soll - hinsichtlich der zeitintensiven Vorgänge nur vier Fälle möglich sind:
|
Tabelle 10:
Varianten bezüglich der Laufzeit | ||
| Einschränkung nach oder Statistik über | Gemeinsame kin. Ketten ausnutzen | AGn-Zerlegung erforderlich |
| Keine, Gestellgelenke und Gelenke pro Glied | nein | nein |
| Glieder in AGn oder Eigentlichkeit | nein | ja |
| Keine, Gestellgelenke, Gelenke pro Glied und Eigentlichkeit | ja | nein |
| Glieder in AGn | ja | ja |
Der Algorithmus kann also mit oder ohne die Zerlegung jedes einzelnen MTs in AGn ablaufen, und das jeweils noch wahlweise in der Variante mit Ausnutzung der Eigenschaften gemeinsamer kinematischer Ketten.
Für diese Varianten wurden folgende Laufzeiten ermittelt:
|
Tabelle 11:
Gemessene Laufzeiten | ||
| Glieder | 12 | 14 |
| Nur Zählen | 9,7s | 9,8min |
| Zählen mit AGn-Zerlegung | 39,2s | 99,4min |
| Nur Zählen, gem. kin. Ketten analysieren | 29,4s | 79,4min |
| Zählen mit AGn-Zerlegung, gem. kin. Ketten ausnutzen | 41,2s | 108,1min |
Daraus lassen sich für die einzelnen Teile des Algorithmus folgende Teillaufzeiten berechnen:
|
Tabelle 12:
Teillaufzeiten | ||
| Glieder | 12 | 14 |
| Ableiten der MTen | 9,7s | 9,8min |
| Analyse der gem. kin. Ketten | 19,7s | 69,6min |
| AG-Zerlegung | 29,5s | 89,6min |
| AG-Zerlegung, gem. kin. Ketten ausnutzen | 11,8s | 28,7min |
Berechnet man daraus nun die durchschnittliche Laufzeit pro Typ, ergibt sich folgendes Bild:
|
Tabelle 13:
Durchschnittliche Laufzeiten für einen einzelnen Typ | ||
| Glieder | 12 | 14 |
| Kettentypen | 6.856 | 318.162 |
| MTen | 195.816 | 11.429.024 |
| Durchschnittliche MTen pro Kettentyp | 29 | 36 |
| Ableiten der MTen, Durchschnitt pro Kettentyp | 1,4ms | 1,8ms |
| Analyse, Durchschnitt pro Kettentyp | 2,9ms | 13,1ms |
| AGn-Zerlegung, Durchschnitt pro Kettentyp | 0,15ms | 0,47ms |
| AGn-Zerlegung, gem. kin. Ketten ausnutzen, Durchschnitt pro Kettentyp | 0,06ms | 0,15ms |
Die AGn-Zerlegung ist also sehr zeitaufwändig im Vergleich zum bloßen Ableiten und Zählen der MTen. Grund: die Ableitung der MTen erfolgt nur einmal pro Kettentyp, die AGn-Zerlegung dagegen für jeden einzelnen dieser MTen. Bei den 14-gliedrigen MTen steigt die Dauer der Statistik-Prozedur durch eine zusätzliche AGn-Zerlegung auf das zehnfache. Daran kann auch das in 2.4. entwickelte Verfahren zum Ausnutzen gemeinsamer kinematischer Ketten nichts ändern - im Gegenteil. Obwohl die Methode beim Erheben der Statistik unter optimalen Umständen arbeitet - von jeder Kette werden alle abgeleiteten MTen untersucht - ist der Algorithmus damit in fast allen Fällen langsamer als die einfachere Variante, die jeden MT einzeln untersucht. Nur wenn die MTen hinsichtlich der Eigentlichkeit eingeschränkt sind oder eine Statistik über die Eigentlichkeit aufgestellt werden soll, bringt die Analyse der gemeinsamen kinematischen Kette einen leichten Zuwachs an Geschwindigkeit, denn sie erspart in diesem Fall die AGn-Zerlegung.
Der Grund dafür, dass das Verfahren im Vergleich so schlecht abschneidet, lässt sich aus obigen Tabellen erkennen. Zwar geht die AGn-Zerlegung mit Hilfe der einmalig aus der Kette gewonnen Informationen tatsächlich wesentlich schneller, doch die Analyse der Kette selbst ist derart zeitaufwändig, dass dieser Vorteil letztendlich ins Gegenteil verkehrt wird. Die Kettenanalyse ist außerdem der Vorgang, dessen Laufzeit mit zunehmender Gliederzahl am stärksten ansteigt. Die Komplexität eines Algorithmus, der Gliedermengen einer Struktur durchsucht, kann sich pro zusätzlichem Glied maximal verdoppeln. Die Kettenanalyse schöpft diese Steigerungsrate der Laufzeit aufgrund ihres Algorithmus vollständig aus. Die anderen Algorithmen, wie z.B. die einfache AGn-Zerlegung, tun dies dagegen nicht ganz, wie in Tabelle 13 zu sehen ist. Deshalb wird die Analyse der gemeinsamen kinematischen Ketten auch bei Strukturen mit noch mehr Gliedern als in dieser Arbeit betrachtet nicht attraktiver. Die einfache AGn-Zerlegung ist in den meisten Fällen vorzuziehen, zumal sie einfacher in der Handhabung ist und eine unter allen Umständen optimale Laufzeit bietet.
