Java Lineare Suche

Bitte aktiviere JavaScript!
Hallo.


Ich habe einen Code geschrieben, der zeigen soll, wie schnell bzw. langsam sich eine lineare Suche verhält. Hierzu wird ein Array mit mit 1000 Plätzen durchsucht. Die eigentliche Suche geschieht zunächst 1000 mal, dann anschließend darauf folgend 30 mal. Beides mal wird ein Mittelwert am Ende gebildet.

Mir ist folgendes aufgefallen:
-je mehr Suchen ich starte, desto geringer wird dann die finale Suchzeit (also das Endergebnis nach den 1000 und 30 mal). Wenn ich jetzt z.B. für die erste innere Schleife eine Zahl von 10.000 und für die äußere 200 statt 1.000 und 30 eingebe, ist die suche laut meinem Code viel schneller als zuvor.
- Der Wert sollte sich doch eigentlich einpendeln und immer ungefähr das selbe anzeigen ?

Kann mir da jemand vielleicht erklären woran dies liegt ? Habe ich einen Fehler gemacht?


Java:
package A2;

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



public class LineareSuche {
    
    public int[] liste; //Array wird definiert als "liste"
    Random zufall = new Random();    // wird erzeugt für Klasse erzeugenUnsortiert()
    int suchzahl; //Dies ist die gesuchte Zahl
    //long zeit;
    //long zeit1000;
    //long zeit30;
    long zeitFinal;
    
    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 = liste[zufall.nextInt(liste.length)]; //legt eine zufällige Suchzahl im Array fest
        for (int i = 0; i < liste.length; i++){
            if(liste[i] == suchzahl){
                return suchzahl; //wenn gefunden wird ausgegeben
            }
        }
                
        return -1; //wenn nicht gefunden
        
        
    }
    
    
    public long suchzeitLinear2() {         //schritte1 = 30 , schritte2= 1000
        
        
        long zeit30=0; //Zeit für 30 Suchen
        
        for (int x=0; x<30;x++) {
        long    zeit1000=0;; // Zeit für 1000 Suchen
        for (int j=0; j<1000;j++ ) {
            
            final long timeStart = System.nanoTime();
            suche();
            final long timeEnd = System.nanoTime();
            long zeit = timeEnd - timeStart; //Dieser Wert soll für Mittelwert benutzt werden
            //System.out.println("Zeit1: "+zeit);
            zeit1000 += zeit;
            //System.out.println("Zeit innen Addiert: "+zeit1000);
            
        }
        zeit30 += zeit1000/1000;
        //System.out.println("Ende innere Schleife / 1000 : "+zeit30);
        }
        
        long zeitFinal=zeit30/30;
        System.out.println(zeitFinal);
        return zeitFinal;
    }
    
    
    

    
    
    public static void main(String[] args) {
        LineareSuche l1= new LineareSuche();
        l1.erzeugeZufallszahl(1000, 2000);
        l1.sortieren();
        //l1.ausgabe();
        l1.suchzeitLinear2();
        //l1.suchzeit30();
    
        
        
    
    }
}


Vielen Dank schon mal und viele Grüße
 
A

Anzeige




Schau mal hier —> (hier klicken)
Mir ist folgendes aufgefallen:
-je mehr Suchen ich starte, desto geringer wird dann die finale Suchzeit (also das Endergebnis nach den 1000 und 30 mal). Wenn ich jetzt z.B. für die erste innere Schleife eine Zahl von 10.000 und für die äußere 200 statt 1.000 und 30 eingebe, ist die suche laut meinem Code viel schneller als zuvor.
- Der Wert sollte sich doch eigentlich einpendeln und immer ungefähr das selbe anzeigen ?

Kann mir da jemand vielleicht erklären woran dies liegt ? Habe ich einen Fehler gemacht?
Der Java-Code wird erst während der Laufzeit anhand der Benutzung zur Laufzeit optimiert.


Wird eine Methode nur einmal (oder analog weniger Male) aufgerufen, lohnt sich ein optimieren nicht - der Code ist ja schon fertig, bevor er optimiert werden würde - stattdessen wird es sehr langsam interpretiert.
Wenn die Methode dann öfter ausgeführt wird, werden "Hotspots", Stellen die oft ausgeführt werden, optimiert. Und je öfter, desto besser optimiert.
In deinem Code kann das im Extremfall dazu führen, dass die suche gar nicht ausgeführt wird, da sie auf das "Ergebnis" deines Programms keine Auswirkung hat ("Dead Code Elimination").


Deshalb nutzt man wie schon gesagt entsprechende Frameworks, die solche Effekte berücksichtigen. Diese führen zb einen "Warmup" durch, ein mehrmaliges Ausführen des Codes, damit er optimiert ist, bevor die eigentliche Messung beginnt und bieten Möglichkeiten, Dead Code Elimination zu verhindern.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben