Laufzeit

[Heinrich500]

Hallo,
ich möchte die Laufzeit meines Sortieralgorithmus messen. Ich will dabei Testinstanzen mit Einträgen zwischen 10.000 und 100.000 erstellen. Wie kann ich das am besten realisieren. Habt ihr vllt einen Tipp, wie man da vorgeht?
Mein Code:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
        
       for(int j = 1 ; j < list.size(); j++){
           T elem=list.get(j);
           int i=j-1;
           while(i>=0 && (elem.compareTo(list.get(i))<0)){
               list.set(i+1,list.get(i));     
               i--;
           }
           list.set(i+1,elem);
        
       }


}

 

[Xyz1]

Ich versuche das mal informal zu erklären....
Du hast zweimal die Methode sort. Zum Bleistift sortA und sortB.
Jetzt erstellt Du Testinstanzen. Das sind zum Bleistift Listen mit 50.000 Elem welche sortiert werden sollen und welche durcheinander und/oder sortiert sind.
Jetzt rufst Du sortA und sortB mit den Testinstanzen auf.
Vorher und Nachher erstellst Du einen Zeitstempel, wann das sortieren anfängt und was das sortieren fertig ist.
Jeweils rechnest Du dann Zeitstempel 2 minus Zeitstempel 1. Das speicherst Du und/oder gibst es aus.
Und dann kannst Du alles vergleichen und zum Bleistift eine Tabelle oÄ erstellen.

 

[Heinrich500]

Wie genau soll der Zeitstempel aussehen?
Und wie kann ich am besten so große Listen in Java erstellen. Eine for Schleife bis 5000 mit Zufallszahlen
?

 

[Xyz1]

jo,
long zs1 = System.currentTimeMillis();

 

[Heinrich500]

Mit dem current Time kann ich also die Zeit messen. Am besten wäre es doch, wenn ich einen anderen Sortieralgorithmus mit meinnem vergleiche.
D.h nachdem ich eine Arraylist aus Zahlen erstellt habe, erstelle mit Current time vor und nach dem Sortierbefehl eine Zeitmessung und betrachte die Differenz. Das gleiche kann ich dann mit meinem anderen Sortieralgo machen. Wäre das die richtige Ausführung?

 

[Xyz1]

jep

 

[Heinrich500]

Vielen Dank für deine Hilfe

 

[mrBrown]

Für Zeitmessungen bei sowas besser System.nanoTime verwenden, currentTimeMillis ist meist zu schlecht aufgelöst.

Außerdem solltest du nicht nur einen Durchlauf messen, sondern viele, und dann den Durchschnitt bilden. Warmup ist auch nicht zu vergessen.


Wenn du’s richtig machen willst, guck dir JMH an, das ist genau für sowas gemacht

 

[Heinrich500]

Gibt es da auch eine Möglichkeit gleich die Werte grafisch darzustellen irgendwie?

 

[Xyz1]

Gibt es da auch eine Möglichkeit gleich die Werte grafisch darzustellen irgendwie?

nein,

Für Zeitmessungen bei sowas besser System.nanoTime verwenden

nein, hoffe das war ein Witz, da die Zeitauflösung so ca 16ms beträgt...

 

[mrBrown]

nein, hoffe das war ein Witz, da die Zeitauflösung so ca 16ms beträgt...

Bei deinen 50_000 vorgeschlagenen Elementen liegt das auf meine lahmen Rechner im Bestcase so bei 0,16ms, das kann man ganz wunderbar mit einer Auflösung von 16ms messen...

 

[kneitzel]

nein,


nein, hoffe das war ein Witz, da die Zeitauflösung so ca 16ms beträgt...

Dem kann ich gerade nicht ganz folgen. Ich interpretiere Deine Aussage, dass die Zeitauflösung bei nanoTime schlechter sein soll?

Aber das ist doch Quatsch. Der Timer ist ja gerade dazu da, um hier noch feinere Werte zu bekommen. Und es gibt diesbezüglich ja auch Dokumentationen wie z.B.:
https://web.archive.org/web/2016030...om/dholmes/entry/inside_the_hotspot_vm_clocks

The relative-time clock is represented by the System.nanoTime() method that returns a "free-running" time in nanoseconds. This time is useful only for comparison with other nanoTime values. The nanoTime method uses the highest resolution clock available on the platform, and while its return value is in nanoseconds, the update resolution is typically only microseconds. However, on some systems there is no choice but to use the same clock source as for currentTimeMillis() - fortunately this is rare and mostly affects old Linux systems, and Windows 98.

Also laut der Aussage dort, ist es mindestens genau so gut aufgelöst aber eher besser (Hier werden nur alte Linux Systeme und Windows 98 genannt.)

Und dann habe ich das mal kurz angetestet:

    public static void doSomething() {
        int arraySize = 500;
        int loopNumber = 500;

        boolean[] array = new boolean[arraySize];
        for (int loop=0; loop < loopNumber; loop++) {
            for (int i=0; i<arraySize; i++) {
                array[i] = !array[i]; 
            }
        }
    }
    public static void main(String[] args) {
        long startMilis = System.currentTimeMillis();
        long startNano = System.nanoTime();

        doSomething();

        long stopMilis = System.currentTimeMillis();
        long stopNano = System.nanoTime();

        System.out.println("currentTimeMillis: " + (stopMilis - startMilis) + " (" + startMilis + " - " + stopMilis + ")");
        System.out.println("nanoTime: " + (stopNano - startNano) + " (" + startNano + " - " + stopNano + ")");
    }

Und da sieht man dann auch den direkten Vergleich. Es mag sein, dass man eh sehr schnell in den ms Sekunden Bereich kommt, so dass man das nicht braucht. (Die Größe mit 500/500 sind bei mir z.B. schon ca. 3ms, die da gemessen werden).
Aber das hat man ja nicht unbedingt. Und wenn man da nur sehr kleine Dinge hat, dann kann das durchaus interessant sein.

Also die Auflösung ist danach bei nanoTime deutlich höher (Wie ja schon erwartet). Da bekomme ich auch verlässig Werte, die < 1ms sind und die relativ stabil sind bei wiederholten Messungen.