|
Attention:
Due to technical maintenance some tools will not be available. See maintenance description for more information. |
|
|
|
|
|
Vertex Successor in amortisierten O(1)
Vertex Successor in amortisierten O(1)
Torsten Will
ZusammenfassungBisher wurde fuer die Aufzaehlung der Nachfolger eines Vertexes ein einfacher Algorithmus mit O(k) verwendet. Hier wird eine Verbesserung untersucht, die die Aufzaehlung der Successoren in Graycode-Reihenfolge ausnutzt und daher amortisierte O(1) hat. |
(Zurück) |
Einleitung
Das verwendete Programm oma. Relevant ist hier, dass zwei verschiedene Versionen getestet wurden.- oma/O(k): Einfache Implementierung mit O(k), bei der jeder Sukzessor von der Wurzel des Vertex-Tries aus neu gesucht wird.
- oma/O(1)): Aufwendigere Implementierung, die im Trie nur so weit hinabsteigt, die die Graycode-Aufzaehlung angibt.
Sequenzdaten
Die Tests wurden mit Sequenzen der BAliBASE durchgefuerht, deren Namen in der Tabelle angegeben sind. Ich habe Datensaetze ausgewaehlt, die lange Sequenzen anthalten (n>400) und k=4 oder k=5 Sequenzen enthalten. Ein weiteres Kriterium war, dass der Alignierungsvorgang eine Weile brauchen wuerde (zwischen 200 und 600 Sekunden).
Testreihe 1
- max htT/gets:Anzahl der get-Zugriffe auf den Hashtable des Vertex-Tries, der die (Vater,Ordinate)->Sohn implementiert. Es wurde das Segment angegeben, das die meisten get-Zugriffe hatte.
- time:Laufzeit in Sekunden.
|
|||||||||||||||||||||||||||||||||
Literatur
 |
 |
 |
 |
 |
|
|
|