Zeitmessung von Algorithmen

[Butterfly]

Hallo,

ich habe ein kleines Problemchen. Es geht um folgendes:
Für mein Informatikstudium soll ich Mergesort, Quicksort und einen randomisierten Quicksort in Java implementieren (schon geschehen). Zum Vergleich der Algorithmen sollen dann verschiedene Listen mit allen drei Algorithmen sortiert werden und die jeweilige Laufzeit gemessen werden. Ich dachte mir, ich mache die Zeitmessung über System.currentTimeMillis(). Ich rufe es direkt vorm ausführen und direkt nach dem ausführen auf und subtrahiere dann die beiden Zeitwerte. Das funktioniert an sich auch wunderbar, blos bekomme ich für meinen Geschmack zu oft 0 als Ergebnis. Schaut man sich die Werte an, die System.currentTimeMillis() ausgiebt, dann sieht man natürlich immer Unterschiede in den Werten, zum Großteil sind sie halt klein.
Ich denke mal, es liegt an der maschineninternen Rundung durch das Subtrahieren. Da kann man ja nichts dagegen machen.

Hat trotzdem jemand eine Idee, wie ich die Zeit messen könnte, ohne bei sehr kleinen Unterschieden immer 0 als Ergebnis zu erhalten?

Falls es wichtig ist: Ich lass jeweils int-Arrays der Länge 5000 sortieren. Mit größeren Arrays muss ich bei meinem Laptop vorsichtig sein, da bekomm ich schnell StackOverflow oder OutOfMemory-Exceptions.

 

[Wildcard]

Das ganze dauert einfach nicht lange genug um irgendetwas sinnvoll messen zu können.
Ruf jede Methode 100 000 mal in einer Schleife auf, dann bekommst du bessere Werte.

 

[Guest]

eventuell bei der Durchschnittsberechung falsch die Division berechnet (ganzzahlig)

 

[Butterfly]

Das ganze dauert einfach nicht lange genug um irgendetwas sinnvoll messen zu können.
Ruf jede Methode 100 000 mal in einer Schleife auf, dann bekommst du bessere Werte.

Wie meinst du das genau? Soll ich dann vor der Schleife und nach der Schleife messen und dann den Durchschnitt bilden?
Dummerweise komme ich dann aber auch in die Verlegenheit, dass ich mein Array 100 000 mal kopieren müsste, da meine Implementation direkt auf dem übergebenen Array arbeitet.

@Gast: Ich berechne momentan noch keine Durchschnitte, sonder blos 2 Werte, die ich dann voneinander abziehe.

 

[Wildcard]

Und? Wozu gibt es System#arraycopy?

 

[blackMamba]

benutz doch einfach die Funktion time in der Linux Konsole, wenn du Linux oder Unix verwendest.
time p args wobei p das Programm und args die Argumente sind.
Wenn du einen Memmory overflow hast, kannste das in der Unix Konsole auch manuel umgehen, bzw den Speicher vergrößern.
z.B. time java -Xms100M -Xmx100M p args
kannst natürlich dein Memory auch auf mehr als 100Mb setzen.

 

[blackMamba]

bzw. wenn du eine Klasse für die Zeitrechnung benutzen willst...also ich benutze dann immer folgende(die haben wir in der Uni gestellt bekommen):

public abstract class Benchmark {
  public abstract void benchmark();
  public long repeat(int count) {
    long start = System.currentTimeMillis();
    for(int i=0; i<count; i++)
        benchmark();
    return (System.currentTimeMillis()-start);
   }
}

 

[Butterfly]

benutz doch einfach die Funktion time in der Linux Konsole, wenn du Linux oder Unix verwendest.
time p args wobei p das Programm und args die Argumente sind.
Wenn du einen Memmory overflow hast, kannste das in der Unix Konsole auch manuel umgehen, bzw den Speicher vergrößern.
z.B. time java -Xms100M -Xmx100M p args
kannst natürlich dein Memory auch auf mehr als 100Mb setzen.

Danke, aber das kann ich nicht verwenden. Ich hab erstens kein Linux drauf und zweitens brauche ich die Messwerte im Java-Programm, da wir dir Werte als grafischen Plot darstellen sollen. Ich denke, ich werds mal mit der Methode von Wildcard probieren.

 

[blackMamba]

ansonsten funktioniert das auch ganz gut mit der abstrakten Benchmark Klasse, die ich hier geschrieben hatte.