Laufzeitmessungen mit Java sind ganz einfach:

long start = System.nanoTime();
tueEtwasDasLangeDauert();
double runTimeInMilliSeconds = (System.nanoTime() - start) / 1000000d;
 
println("Das hat " + runTimeInMilliSeconds + "ms gedauert!);

Hier muss nur noch statt tueEtwasDasLangeDauert(); das Programm eingefügt werden, dessen Laufzeit ermittelt werden soll.

Wenn man beispielsweise die Laufzeit einer Implementierung von SelectionSort ermitteln möchte, dann lässt sich mit dem oben beschriebenen Anweisungsmuster so realisieren:

int[] sortiere(int[] liste) {
  for (int bereichsGrenze = 0; bereichsGrenze < liste.length; bereichsGrenze++) {
    int kleinstes = bereichsGrenze;
 
    for (int i = bereichsGrenze; i < liste.length; i++) {
      if (liste[i] < liste[kleinstes]) {
        kleinstes = i;
      }
    }
 
    int tmp = liste[bereichsGrenze];
    liste[bereichsGrenze] = liste[kleinstes];
    liste[kleinstes] = tmp;
  }
 
  return liste;
}
 
void printArray2(int[] array) {
  for (int i = 0; i < array.length; i++) {
    print(array[i]);
 
    if (i < array.length - 1) {
      print(", ");
    }
  }
 
  println();
}
 
void setup() {
  int[] liste = { 25,  17,  32,  56,  25,  19,   8,  66,  29,   6,  20,  29 };
 
  print("unsortiert: ");
  printArray2(liste);
 
  print("sortieren: ");
  long start = System.nanoTime();
  liste = sortiere(liste);
  double runTime = (System.nanoTime() - start) / 1000000d;
 
  println(runTime + "ms");
 
  print("sortiert: ");
  printArray2(liste);
}

Wie stabil sind die Ergebnisse von Laufzeitmessungen, wenn man ein und dieselbe Liste mehrfach mit demselben Programm sortiert? Wir probieren das mit dem folgenden Testprogramm aus.

int[] array = new int[1000];
 
for (int j = 0; j < array.length; j++) {
  array[j] = (int)random(0, array.length);
}
 
for (int i = 0; i < 1000; i++) {
  long start = System.nanoTime();
  sortiere(array.clone());
  double runTime = (System.nanoTime() - start) / 1000000d;  
  println("Laufzeit: " + runTime + "ms");
}  

Wir könnten folgende Ausgabe erhalten:

laufzeit: 0.184849ms
laufzeit: 0.184839ms
laufzeit: 0.190099ms
laufzeit: 0.1848ms
laufzeit: 0.18484ms
laufzeit: 0.184819ms
...

Ziel der folgenden Untersuchungen ist es, das Laufzeitverhalten von Sortieralgorithmen systematisch zu ermitteln und die Ergebnisse genauer zu analysieren.

Hierzu bestimmen wir die Laufzeit $t(n)$ in Abhängigkeit der Listenlänge $n$ für wachsende Listenlängen (z.B. $n = 1000, 2000, ...$).

Die zu sortierenden Listen werden mit Zufallszahlen gefüllt. Bei der Erzeugung der Testlisten wird der Zahlenbereich, aus dem die Zufallszahlen stammen, an die Listengröße angepasst, um ähnliche Ausgangssituationen zu erhalten.

Das folgende Programm kann auf diese Weise systematisch die Laufzeiten für bestimmte Listenlängen ermitteln:

for (int anzahl = 1000; anzahl <= 10000; anzahl += 100) {
  int[] array = new int[anzahl];
 
  for (int i = 0; i < array.length; i++) {
    array[i] = (int)random(0, array.length);
  }    
 
  long start = System.nanoTime();
  sortiere(array);
  double runTime = (System.nanoTime() - start) / 1000000d;  
  println("Laufzeit bei " + anzahl + " Einträgen: " + runTime + "ms");
}

Laufzeitmessungen werden in der Praxis durchgeführt, um das Laufzeitverhalten eines Programms unter Realbedingungen zu ermitteln.

Aus systematisch durchgeführten Laufzeitmessungen kann man oft Gesetzmäßigkeiten erschließen, wie die Laufzeit von den zu verarbeitenden Daten abhängt.

Bei Laufzeitmessungen muss man aber sehr genau darauf achten, dass sie unter gleichen Bedingungen erfolgen. Ein Wechsel des Rechners führt in der Regel zu anderen Ergebnissen. Auch Änderungen in der Implementierung wirken sich in der Regel auf die Messergebnisse aus. Selbst bei ein und demselben Rechner und derselben Implementierung können sich die Bedingungen ändern, da oft mehrere Prozesse gleichzeitig ablaufen.

Ergebnisse von Laufzeitmessungen sind also kaum auf andere Systeme (andere Rechner, andere Programmiersprachen) übertragbar. Um diese Schwierigkeit zu überwinden, soll im nächsten Abschnitten ein anderer Weg zur Beschreibung der Berechnungskomplexität beschritten werden.