Laufzeit berechnen?

[b1zarRe]

Gibt es in Java eine Methode um die Laufzeit zu berechnen? In Form von den Landau Symbolen wie O(n²) oder ähnlich? Oder benutzt ihr nur die System.currentTimeMillis(); Methode?

 

[Marco13]

Das eine hat mit dem anderen nicht viel zu tun. (Nicht "nichts", aber nicht viel). Die Landausache verwendet man ohnehin eher für "elementare" Dinge (Zugiffszeiten bei Listen oder Maps, Dinge wie Suchen und Sortieren) wenn man nicht gerade einen neuen Algorithmus in einem wissenschaflichen Paper beschreibt... Für den Rest gibt's System.nanotime, Profiler, und den KPD-Index. (Kippen pro Durchlauf )

 

[b1zarRe]

Also Landau Symbole eher in der Theorie? Und garnicht in Java?

Ich würde zb gerne sehen, wielange eine Methode a im Gegensatz zu einer Methode b brauch.
Beispielsweise eine Methode a die eine For Schleife hat und eine Methode b die 2 oder 3 Innere Forschleifen hat. Ich möchte dann vergleichen können, welche davon schneller ist (wird wohl die mit einer Schleife sein ). Aber wie kann ich das genau bewerkstelligen?

Ich habe bisher probiert, nach der Methode a System.currenttimemillis(); zu machen bzw. nano und dann nach methode b genau das gleiche. Und dann das eine vom anderen zu subtrahieren... macht ihr das auch so? oder irgendwie (noch) effizienter?

 

[T7V]

Es gibt zum Beispiel die methode currentTimeMillis().
Diese liefert dir die Zeit (UTC), welche seit dem 1 Januar 1970 (oder so) vergangen ist in Millisekunden ( als long).
Du könntest diese Methode am Anfang und Ende einbauen, in Variablen abspeichern und einfach abziehen.
Dann bliebe logischerweise die Laufzeit in Millisekunden.

 

[b1zarRe]

Ok, vielen Dank

 

[Marco13]

Die reine Zeitmessung, wie T7V schon angedeutet hat:

long before = System.nanoTime();
rechne();
long after = System.nanoTime();
double durationMS = (after-before)/1e9;
System.out.println("Zeit: "+durationMS+" ms");

Die Sache mit den Schleifen ist aber zu pauschal. Sowas wie

for (int i=0; i<1; i++) { /* mache nichts */ }
for (int i=0; i<1; i++) { /* mache nichts */ }
for (int i=0; i<1; i++) { /* mache nichts */ }

wird sicher schneller gehen als

for (int i=0; i<100000; i++) { macheViel(); }

Die Landau-Symbole beschreiben die asymptotische Laufzeit - das ist wichtig wenn man sich z.B. die Frage stellt, ob es besser ist, eine LinkedList oder eine ArrayList zu verwenden, oder ob man für eine Wegsuche im Graphen eine BFS oder einen Dijkstra mit Fibonacci-Heap verwende soll. Wie gesagt, das hat mit der "tatsächlichen" Zeit nur indirekt zu tun (eben nur... asymptotisch )

 

[b1zarRe]

Ok, ich danke Euch!

Jep, dass mit der asymptotischen Laufzeit besprechen wir gerade im Studium.... Aber gibt es dennoch dafür keine Java Klasse, welche das abschätzen kann? Denke ich werde die o.g. Methodik benutzen und klappt auch wunderbar... Aber wenn es doch sowas asymptotisches gibt, wäre es nett zu erfahren.

 

[Marco13]

Theoretisch wäre es vielleicht in gewissen Grenzen möglich, Code zu analysieren, und wirklich die asymptotische Laufzeit zu bestimmen - zumindest in Trivalfällen wie

for (int i=0; i<n; i++) { System.out.println(i); }

sollte sich das O(n) da noch herleiten lassen. "Praktisch" sieht das anders aus, und wo die Grenzen sind ist eben die Frage.

Man könnte auch ganz dumm-dreist approximieren:

for (int n=1; n<100; n++)
{
    timeFor(runWith(n)); 
}

Wenn dort als Laufzeiten rauskommen
n = 1 : 1 Sekunde
n = 2 : 2 Sekunden
n = 3 : 3 Sekunden
...
dann würde vielleicht ein Linearer Zusammehang nahe liegen, aber das funktioniert eben so NICHT, weil man nur durch Messung nicht die asymptotische (genau darum geht es ja) Laufzeit bestimmen kann. (Aber zugegeben: Um zwei Sortierverfahren über den Daumen anzuschätzen kann es schon helfen, sich mal die Zeiten für n=1000, n=1000000 und n=1000000000 anzusehen )