Java Lineare-Suche Zeitmessung

[slitec]

Hallo,

ich habe vorab 2 Fragen, allerdings sollte zuvor der Code erklärt werden:

Ich habe hier einen Code geschrieben, der die Dauer (Zeit) der Linearen-Suche misst. Hierzu wird in der Methode suchzeitLinear() die Methode
suche() 1000 mal ausgeführt (schritte2), die Zeit addiert und dann ein Mittelwert gebildet. Anschließend wird dies 30 mal mit 30 verschiedenen Zahlen durchgeführt um letztendlich nochmals einen Mittelwert zu bilden. Somit kommen wir auf 30.000 Durchläufe um einen einigermaßen zuverlässigen Durchschnittswert zu bekommen.

Nun zu meinen Fragen:

1. Ich weiß, dass die Methode suchen() beim mehrmaligen Ausführen optimiert wird. Hierzu habe ich mir überlegt ein "Warmup" einzuführen sodass diese Methode suchen() zuvor erst mal 1000 vor der Zeitmessung ausgeführt wird mit jeweils einer unterschiedlicher Suchzahl, damit diese beim Messen dann schon optimiert ist.
--> Reicht dieses Warmup somit aus, damit ein einigermaßen zuverlässiger Messwert gemessen werden kann?

2. Ist es auch so, dass die gesuchten Zahlen vielleicht im Speicher geladen werden ? Denn manche Zahlen werden nach dem Warmup deutlich schneller gefunden als andere Zahlen. Somit müssten doch dann die bereits gesuchten Zahlen schneller gefunden werden?
--> Wenn dies der Fall ist, gibt es vielleicht eine Möglichkeit den Speicher nach jeder Suche zu leeren, damit alle Suchzahlen die selbe Voraussetzungen besitzen und somit auch die Zeitmessung nicht verfälscht wird?

Ich bedanke mich im Voraus für die Antworten.

Vollständiger Code:

package a3;


import java.util.Random;   
import java.util.Arrays;



public class LineareSuche {
    
    int[] liste; //Array wird definiert als "liste"
    Random zufall = new Random();    // wird erzeugt für Klasse erzeugenUnsortiert()
    int suchzahl; //Dies ist die gesuchte Zahl
    int schritte;

    
    public LineareSuche(){
    }
    
    public void erzeugeZufallszahl(int plätze,int oberGrenze) {
        //Erzeugt nicht gleichverteilte Zufallszahlen (doppelte sind möglich)
        
        liste = new int [plätze];
        //Anzahl an Plätze wird übergeben
        
        for (int i=0; i<liste.length;i++) {
            liste[i] = zufall.nextInt(oberGrenze);
            // Liefert eine int-Pseudo-Zufallszahl im Bereich von 0 bis oberGrenze
        }
    }
    
    public void sortieren(){
        Arrays.sort(liste);
    }
    
    
    
    public void ausgabe() {
        for (int i=0; i<liste.length; i++) {
            System.out.println(liste[i] + " || Index: " + (i));
        }
    }
    
    
    
    
    public int suche(int suchzahl) {
        
        //suchzahl = liste[zufall.nextInt(liste.length)]; //legt eine zufällige Suchzahl im Array fest
        for (int i = 0; i < liste.length; i++){
            schritte++;
            if(liste[i] == suchzahl){
                return suchzahl; //wenn gefunden wird suchzahl zurückgegeben
                
            }
        }
                
        return -1; //wenn nicht gefunden
        
        
    }
    
    
    public long suchzeitLinear(int schritte1,int schritte2,int warmup) { //schritte1 = 30 , schritte2= 1000 //warmup = 1000
        
        
        /*for(int y=0; y<warmup; y++) {
            suchzahl = 0;
            suche(suchzahl);
        } */
        
        long zeit1=0; //Zeit für 30 Suchen
        
        for (int x=0; x<schritte1;x++) {
            
        long    zeit2=0;; // Zeit für 1000 Suchen
        schritte=0;
        
        for (int j=0; j<schritte2;j++ ) {
            
            final long timeStart = System.nanoTime();
            suche(suchzahl);
            final long timeEnd = System.nanoTime();
            long zeit = timeEnd - timeStart;
            zeit2 += zeit; //Zeit innere Schleife addiert
        
            
        }
        zeit1 += zeit2/schritte2; //Zeit äußere Schleife addiert
        System.out.println("Suchzahl"+x+": " +suchzahl+"      Zeit: "+zeit2/schritte2+"      Schritte: "+schritte);
        //Für Anzahl an schritte2 wird die Zeit wiedergegeben sowie die Schritte
    
        }
        
        long zeitFinal=zeit1/schritte1; //Finale Zeit
        System.out.println("Suchzeit: "+zeitFinal+" Nanosek.");
        return zeitFinal;
    }
    
    
    
    
    
    
    public static void main(String[] args) {
        LineareSuche l1= new LineareSuche();
        l1.erzeugeZufallszahl(10000, 20000);
        l1.sortieren();
        //l1.ausgabe();
        l1.suchzeitLinear(30,1000,100000);
        
        
    }
}

Code der Methode suchzeitLinear():

    public long suchzeitLinear(int schritte1,int schritte2,int warmup) { //schritte1 = 30 , schritte2= 1000 //warmup = 1000
        
        
        /*for(int y=0; y<warmup; y++) {
            suchzahl = 0;
            suche(suchzahl);
        } */
        
        long zeit1=0; //Zeit für 30 Suchen
        
        for (int x=0; x<schritte1;x++) {
            
        long    zeit2=0;; // Zeit für 1000 Suchen
        schritte=0;
        
        for (int j=0; j<schritte2;j++ ) {
            
            final long timeStart = System.nanoTime();
            suche(suchzahl);
            final long timeEnd = System.nanoTime();
            long zeit = timeEnd - timeStart;
            zeit2 += zeit; //Zeit innere Schleife addiert
        
            
        }
        zeit1 += zeit2/schritte2; //Zeit äußere Schleife addiert
        System.out.println("Suchzahl"+x+": " +suchzahl+"      Zeit: "+zeit2/schritte2+"      Schritte: "+schritte);
        //Für Anzahl an schritte2 wird die Zeit wiedergegeben sowie die Schritte
    
        }
        
        long zeitFinal=zeit1/schritte1; //Finale Zeit
        System.out.println("Suchzeit: "+zeitFinal+" Nanosek.");
        return zeitFinal;
    }

 

[mihe7]

Du verfälscht Dein Ergebnis schon dadurch, dass Du zwischen den Schritten die Zeit misst. Das haben wir in einem anderen Thread schon mal erklärt.

Für das Warmup würde ich einfach in zigtausend Iterationen die Klasse instantiieren und die Zeitmessung durchführen. Ggf. noch auf den GC achten.

 

[slitec]

Du verfälscht Dein Ergebnis schon dadurch, dass Du zwischen den Schritten die Zeit misst. Das haben wir in einem anderen Thread schon mal erklärt.

Für das Warmup würde ich einfach in zigtausend Iterationen die Klasse instantiieren und die Zeitmessung durchführen. Ggf. noch auf den GC achten.

Ich messe die Zeit aber doch nicht zwischen den Schritten oder ? Ich messe die Zeit ja nur solange die Methode suche() läuft. Oder sollte ich die Zeitmessung innerhalb der Methode suche() ausführen?

Was genau meinst du mit instantiieren ?

 

[mihe7]

Ich messe die Zeit ja nur solange die Methode suche() läuft.

Schon, aber für die Messung musst Du ja auch Methoden aufrufen (System.currentTime...) Es reicht, wenn Du einmal vor der (inneren) Schleife und einmal außerhalb misst.

Was genau meinst du mit instantiieren ?

Neue Objekte erzeugen. Im Prinzip so etwas:

        for (int i = 20; i >= 0; i--) {
            LineareSuche l = new LineareSuche(i == 0 ? 1L : System.currentTimeMillis());
            l.erzeugeZufallszahl(10000, 20000);
            l.sortieren();            
            l.suchzeitLinear(30,1000, i == 0);
        }

wobei der letzte Parameter von suchzeitLinear in dem Fall angibt, ob eine Ausgabe erfolgen soll oder nicht.

 

[slitec]

Schon, aber für die Messung musst Du ja auch Methoden aufrufen (System.currentTime...) Es reicht, wenn Du einmal vor der (inneren) Schleife und einmal außerhalb misst.

Ich rufe aber doch die Methode System.nanoTime() für die Messung schon auf in der Methode suchzeitInterpolation() ? Versteh nicht ganz was genau du mit dieser Aussage meinst?

 

[mihe7]

1. Ich sehe keine Methode suchzeitInterpolation().
2. Was ich damit meine: der Methodenaufruf von System.nanoTime (oder System.currentTime... oder was auch immer) benötigt auch ein klein wenig Zeit und zusätzlich ist der relative Fehler größer, je kürzer die Abstände sind (z. B. bekommst Du je nach Betriebssystem die Zeit nicht mit einer Auflösung von 1 ns zurück). Wenn Du die Messwerte addierst, addiert sich damit auch der Fehler.