Laufzeit bei rekursiver Methode messen

[Sesostris]

Hallo,

folgendes Beispiel für eine typisch rekursive Funktion: die Fibonacci-Folge

public class Recursive {
    public long fibonacci(int n) {
    	if (n == 0) return 0;
    	if (n == 1) return 1;
    	return fibonacci(n-1)+fibonacci(n-2);
    }
}

Laut meiner Vorgabe sollte es eine Instanzvariable runtime geben, die die Laufzeit in Millisekunden der zuletzt ausgeführten Methode speichert.

public class Recursive {
    public long runtime;

    public long fibonacci(int n) {
    	runtime = System.currentTimeMillis();
    	long fibonacci2 = fibonacci2(n);
    	runtime = System.currentTimeMillis() - runtime;
    	return fibonacci2;
    }

    private long fibonacci2(int n) {
    	if (n == 0) return 0;
    	if (n == 1) return 1;
    	return fibonacci2(n-1)+fibonacci2(n-2);
    }
}

Ginge das auch irgendwie eleganter?

 

[Fab1]

Hallo,


schau mal hier unter Java:

Performance-Messung - Wissensbasis

sicherlich sehr hilfreich.

Quelle: Performance-Messung - Wissensbasis


Zeitmessung mit System.currentTimeMillis():
Die Funktion System.currentTimeMillis() bietet im besten Fall eine Auflösung im Millisekundenbereich. Die tatsächliche Auflösung hängt jedoch vom eingesetzten Betriebssystem und dessen Konfiguration ab. Der zurückgegebene Wert bezieht sich auf die seit dem 01.01.1970 00:00 (UTC) vergangenen Millisekunden. Quelle: Java Dokumentation (System (Java 2 Platform SE 5.0))). Damit ist eine absolute Zeitangabe möglich.
Bewertung:
Für Performance-Messungen ist diese Funktion aufgrund ihrer Ungenauigkeit jedoch nur bedingt geeignet.

Zeitmessung mit System.nanoTime():
Mit Java 1.5 wurde die Funktion System.nanoTime() eingeführt. Diese wählt die genaueste verfügbare Zeitquelle aus und gibt deren Wert in Nanosekunden zurück. Der Bezugszeitpunkt der Zeitangabe oder die tatsächliche Genauigkeit bleiben unbekannt. Aus diesen Gründen kann die Angabe nur zur Berechnung von verstrichener Zeit benutzt werden. Quelle: Java Dokumentation (System (Java 2 Platform SE 5.0))).

 

[Sesostris]

Aber das ändert nichts daran, dass die Messung der Laufzeit so unelegant in zwei Methoden aufgeteilt ist.
Trotzdem danke für den Tipp; ich habe es abgeändert.

 

[Gast2]

ne zweite Methode brauchst du ja nicht unbedingt. Du kannst die Zeitmessung auch in der aufrufenden Klasse machen.

 

[Sesostris]

Du meinst so?

Recursive foo = new Recursive();
foo.runtime = System.nanoTime();
long fibonacci = foo.fibonacci(50);
foo.runtime = System.nanoTime() - foo.runtime;

Aber angenommen, ich rufe foo.fibonacci(...) mehrmals auf und will immer die letzte Laufzeit wissen, dann müsste ich ebenfalls mehrmal dieses Gerüst foo.runtime = ... usw. schreiben. Genau das wollte ich mir ja sparen, indem ich die Laufzeitmessung mit ins Objekt packe.

 

[Gast2]

dann müsste ich ebenfalls mehrmal dieses Gerüst foo.runtime = ... usw. schreiben

...oder das ganze in ne Schleife packen.

 

[nillehammer]

Du könntest fibonaci so umschreiben, dass sie ein Array mit zwei long-Elementen returnt. Das erste ist das eigentliche Ergebnis, das zweite die Laufzeit. Über die Eleganz lässt sich streiten, aber so kommst Du ohne Instanzvariable und ohne externe Zeitmessung aus.