Uni-Konstanz Uni-Konstanz
Fachbereich Informatik und Informationswissenschaft   Grundpraktikum Informatik  
Wagner / Willhalm / Schulz

Teil IV - Auswertung / Laufzeitmessung

Die Laufzeitmessung mit dem Profiler hprof hat sich als ungeeignet erwiesen. Stattdessen kann unmittelbar vor und nach der eigentlichen Berechnung, die gemessen werden soll, die Zeit genommen werden (mit der Methode System.currentTimeMillis() ). Die Differenz dieser beiden Werte ist dann die Zeit in Millisekunden, die für die Berechnung benötigt wurde. Um Vergleichen zu können sollte zumindest für jede Testreihe immer derselbe Rechner verwendet werden, auf dem ausser der Laufzeitmessung möglichst wenige Prozesse laufen, welche die Messung verfälschen können.
  1. Zufallszahlen sortieren
    Die Dateien «~willhalm/lehre/inf4_W00/zufallszahlen/random.*» enthalten Zufallszahlen zwischen 0 und 30000.

  2. Kürzeste Verbindungen
    50 Anfragen in «~willhalm/lehre/inf4_W00/fahrplan/auswertung-anfragen.au»

  3. rRNA Vergleich
    rRNA Datenbestand in «~willhalm/lehre/inf4_W00/rRNA/16s-rRNA-schnitt.FASTA»;
    Für jede rRNA-Sequenz in der Datei «~willhalm/lehre/inf4_W00/rRNA/16s-rRNA-schnitt-ref.FASTA» werden die Sequenzen aus dem Datenbestand nach Ähnlichkeit sortiert.
    Dazu wird ausgehend von jeweils zwei Sequenzen ein JDSL-IncidenceListGraph aufgebaut (wir werden also keinen speziellen rRNA-Graphen implementieren) und darin mit Dijkstra's Algorithmus ein kürzester Weg gesucht.

  4. Dijkstra's Algorithmus auf Zufallsgraphen
    Die Zufallsgraphen sind
    • «~willhalm/lehre/inf4_W00/graphen/zufallsgraph????»
    • «~willhalm/lehre/inf4_W00/graphen/exponentialgraph????»
    Für die Knoten 1 bis 10 berechnet Dijkstra's Algorithmus für jeden erreichbaren Knoten die Länge eines kürzesten Weges (d.h. kein zusätzliches Abbruchkriterium; der Algorithmus endet, wenn die Priority Queue leer ist)
Generell sollte jede der vier Berechnungen mit jeder "normalen" Priority Queue (d.h. Queues 1-8) durchgeführt werden, sowie mit der Bucket Queue, wobei die Priority Queue zugrunde gelegt wird, die bei der jeweiligen Berechnung die schnellsten Ergebnisse liefert. Für 1. - 3. kommt noch die Bucket Queue dazu, die eine Pseudo-Queue benützt.
letzte Änderung: 19.07.2016