Java Lineare-Suche Zeitmessung


slitec

Grünschnabel
#1
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:
Java:
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():
Java:
    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;
    }
 

Bratkartoffel

gebratene Kartoffel
Premium-User
#2
Hi,

das was du machst / machen willst gibt es schon ;)
Das ganze nennt sich "JMH":
OpenJDK: jmh
JMH - Java Microbenchmark Harness

Wie du schon selber festgestellt hast, ist das ganze gar nicht so trivial wie es auf den ersten Blick scheint. Das mit dem Warmup von 1000 Runden sollte ausreichen, hier würde ich aber noch ein paar Tests machen. Dass die Suche manchmal schneller ist liegt wohl daran, dass er die gesuchte Zahl mal früher und mal später findet. Das ist etwas problematisch wenn man nicht deterministische Daten nimmt.

Grüsse,
BK
 

slitec

Grünschnabel
#3
Hi,

das was du machst / machen willst gibt es schon ;)
Das ganze nennt sich "JMH":
OpenJDK: jmh
JMH - Java Microbenchmark Harness

Wie du schon selber festgestellt hast, ist das ganze gar nicht so trivial wie es auf den ersten Blick scheint. Das mit dem Warmup von 1000 Runden sollte ausreichen, hier würde ich aber noch ein paar Tests machen. Dass die Suche manchmal schneller ist liegt wohl daran, dass er die gesuchte Zahl mal früher und mal später findet. Das ist etwas problematisch wenn man nicht deterministische Daten nimmt.

Grüsse,
BK

Danke erst mal für die Antwort. Die Daten erzeuge ich wie folgt:

Java:
suchzahl = liste[zufall.nextInt(liste.length)];
Dabei müsste es sich doch eigentlich um deterministische Daten handeln ?

Kann ich damit also auch ausschließen, dass die Suchzahlen im Speicher gespeichert werden und somit schneller gefunden werden als nicht bereits gesuchte Zahlen?