Java Lineare-Suche Zeitmessung

S

slitec

Mitglied
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;
    }
 
mihe7

mihe7

Top Contributor
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.
 
S

slitec

Mitglied
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

mihe7

Top Contributor
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:
Java:
        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.
 
S

slitec

Mitglied
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

mihe7

Top Contributor
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Java Lineare Suche Java Basics - Anfänger-Themen 1
V_Fynn03 Beliebiges Element in einer Liste löschen (Java)(Lineare Datenstrukturen) Java Basics - Anfänger-Themen 9
TimoN11 Java Klassen Global einbinden Java Basics - Anfänger-Themen 1
H Binominalkoeffizient tail-rekursiv in java darstellen Java Basics - Anfänger-Themen 0
H Audio in Java Java Basics - Anfänger-Themen 3
I Erklärung zum Java Code Java Basics - Anfänger-Themen 2
AlexVo String zu Java Anweisung getString("*** java code ***") Java Basics - Anfänger-Themen 19
R Java (Eclipse) "Lagerverwaltung" HILFE Java Basics - Anfänger-Themen 13
TimoN11 Java - Eine oder mehrere Eingaben möglich machen Java Basics - Anfänger-Themen 6
M Rekursive Java-Methode Java Basics - Anfänger-Themen 13
M Java Spiel wie Wer wird Millionär Java Basics - Anfänger-Themen 1
bafou Dreieckszahlen in java Java Basics - Anfänger-Themen 3
P Best Practice Druck aus Java Anwendung in MacOs Java Basics - Anfänger-Themen 0
G Java 2-dimensionalen int-Array Summe Java Basics - Anfänger-Themen 2
B java.time Duration mit Kommazahl? Java Basics - Anfänger-Themen 4
Devin Wo kann man einen Java Lehrplan finden? Java Basics - Anfänger-Themen 5
KogoroMori21 Java Datum Differenz (kleiner Fehler) Java Basics - Anfänger-Themen 10
O Java Weinachtsbaum in einem Bilderramen Java Basics - Anfänger-Themen 5
F Java Programm, das kleine Buchstaben in einem String zählen soll und bei großen Buchstaben oder Sonderzeichen abbrechen soll. Java Basics - Anfänger-Themen 5
Gaudimagspam Dringend Java Hilfe benötigt Java Basics - Anfänger-Themen 19
M Java Kompilieren über Package grenzen hinaus Java Basics - Anfänger-Themen 4
N java.util.InputMismatchException Fehler Java Scanner Java Basics - Anfänger-Themen 1
Gaudimagspam BMI in Java implementieren Java Basics - Anfänger-Themen 38
C Was ist nötig für ein Java-Programm auf Server für Website Java Basics - Anfänger-Themen 18
F Fehlermeldung java.lang.NullPointerException Java Basics - Anfänger-Themen 4
S Sprung mit Java (GameGrid) Java Basics - Anfänger-Themen 9
Devin Wie lange braucht man um Java zu beherrschen und wie kann man es am schnellsten erlernen? Java Basics - Anfänger-Themen 7
G Java Klassen und Instanzmethoden Java Basics - Anfänger-Themen 15
Zrebna Frage zum "Referenzen-konzept" in Java Java Basics - Anfänger-Themen 8
C java.util Timer läuft zu langsam? Java Basics - Anfänger-Themen 1
T Klassendiagramm in Java überführen Java Basics - Anfänger-Themen 2
Gaudimagspam Caesars Code entziffern in Java Java Basics - Anfänger-Themen 8
V Gehalt berechnen in Java Java Basics - Anfänger-Themen 6
java3690 Java- liste füllen ud die werte addieren Java Basics - Anfänger-Themen 13
justemii Gehalt berechnen - Aufgabe Java-Programm Java Basics - Anfänger-Themen 9
P Mit iPad Java lernen Java Basics - Anfänger-Themen 15
W Java in Exe Datei umgewandelt, Ressourcen fehlen (Bilder und Audiodateien) Java Basics - Anfänger-Themen 1
N Best Practice How can I creat a programm with java under windows 10 in order to open an spreadsheet in libreoffice calc format Java Basics - Anfänger-Themen 11
T Start-Activity für Java Maven Web-Anwendung festlegen Java Basics - Anfänger-Themen 2
J Java FX - Label aktualisieren Java Basics - Anfänger-Themen 1
A Hilfe bei Java Projekt Java Basics - Anfänger-Themen 4
G Java Bruchrechner Addition, Multiplikation... Java Basics - Anfänger-Themen 12
M Java Einstellung von Apache POI für MS Word Erstellung mit Eclipse Java Basics - Anfänger-Themen 6
B Exception in thread "AWT-EventQueue-0" java.util.ConcurrentModificationException Java Basics - Anfänger-Themen 8
T Java Swing - Dreieck zeichnen mit verschiedenen Variablen Java Basics - Anfänger-Themen 8
P Wie für EIN Java Programm von 64bit Java (=Standard) auf 32bit Java Installation (Windows) umschalten? Java Basics - Anfänger-Themen 6
C Suche Nachhilfe in Java Java Basics - Anfänger-Themen 5
B java.io.OutputStream zu java.io.InputStream konvertieren Java Basics - Anfänger-Themen 18
A Scanner Befehl Java Anfänger Java Basics - Anfänger-Themen 8
M Java entity und wertklassen Java Basics - Anfänger-Themen 2
G Java Vererbung Java Basics - Anfänger-Themen 8
M Java Klasse Object Java Basics - Anfänger-Themen 5
M Java GUI label ändert sich erst zum Schluss Java Basics - Anfänger-Themen 4
G Java Lambda Ausdrücke Java Basics - Anfänger-Themen 19
M Java GUI explorer aufrufen um Pfad zu bekommen Java Basics - Anfänger-Themen 3
M Java Anweisungen Java Basics - Anfänger-Themen 4
M Java 8 Lambda Expression Java Basics - Anfänger-Themen 1
S Java Array Probleme Java Basics - Anfänger-Themen 3
Mr_Kleeblatt Operatoren if (arri[i] != "test.java"&& arri[i] != "test.class") Java Basics - Anfänger-Themen 3
S Java Stream API Java Basics - Anfänger-Themen 6
S Java Array Problem... Java Basics - Anfänger-Themen 2
M Java Listen Java Basics - Anfänger-Themen 4
G Java Object value und entity? Java Basics - Anfänger-Themen 2
X Kurzes Java-Programm, das sich komisch verhält Java Basics - Anfänger-Themen 6
_Zabuza_ Erste Schritte Wie am effektivsten Java lernen als Anfänger? Java Basics - Anfänger-Themen 12
G Java Dateisystem Java Basics - Anfänger-Themen 4
G Java charAt Methode Java Basics - Anfänger-Themen 10
L Java lernen Java Basics - Anfänger-Themen 1
G Rot-Schwarz-Bäume Java Java Basics - Anfänger-Themen 10
G Java LinkedList remove Methode Java Basics - Anfänger-Themen 5
G Java LinkedList Java Basics - Anfänger-Themen 6
G Java eingelesene Zahlen Java Basics - Anfänger-Themen 2
Y Java andere Klasse aufrufen Java Basics - Anfänger-Themen 6
I Java zweidimensionales array befüllen mit for-schleife Java Basics - Anfänger-Themen 2
Z vereinfachtes Wörterbuch in java modellieren Java Basics - Anfänger-Themen 10
L Zufälliges Objekt aus der ArraylList ohne java.util.Random Java Basics - Anfänger-Themen 56
S Geht das bei Java ? Java Basics - Anfänger-Themen 11
T Java Anfänger mit konkreten Fragen Java Basics - Anfänger-Themen 2
C Java Spiel Java Basics - Anfänger-Themen 3
R Java SQL Fehler! Java Basics - Anfänger-Themen 4
CT9288 Fragen zu Java Java Basics - Anfänger-Themen 16
M Java Version Verständnisfrage Java Basics - Anfänger-Themen 16
G Java equals() Methode Java Basics - Anfänger-Themen 9
G Java Objekte auf Duplikate testen Java Basics - Anfänger-Themen 4
D Java Einstieg Java Basics - Anfänger-Themen 4
K Java Projekt Hilfe Java Basics - Anfänger-Themen 5
B Java Mail -> Mail senden, ist aber nich in IMAP unter "Gesendet" Java Basics - Anfänger-Themen 3
jmar83 Bluetooth-Zugriff, braucht es dazu plattformabhängige Libraries oder kann das Java mittlerweile selbst? Java Basics - Anfänger-Themen 10
E Macht Java Rechenfehler beim Potenzieren und Mod? Java Basics - Anfänger-Themen 5
F Java GUI-PaintComponent funktioniert nicht Java Basics - Anfänger-Themen 1
Z Methode zum Heraufinden von Anagrammen ohne Java API, Ausnahme String Java Basics - Anfänger-Themen 14
K Java Aufgaben-Wie ran gehen? Java Basics - Anfänger-Themen 6
S Kreisberechnung3 Buch: Programmieren lernen mit Java von Hans-Peter Habelitz Java Basics - Anfänger-Themen 39
V Ersätze für Java-Scanner Java Basics - Anfänger-Themen 9
M Quiz in Java programmieren mit Array Java Basics - Anfänger-Themen 8
D java.lang.NullPointerException Java Basics - Anfänger-Themen 19
J Welche Java-Version installieren Java Basics - Anfänger-Themen 9
A Java.util.Arrays Java Basics - Anfänger-Themen 15
X Reverse algorithm engineering (Java code) Java Basics - Anfänger-Themen 6
C Wie habt Ihr angefangen mit der Java Programmierung, ohne Programmiervorkenntnisse Java Basics - Anfänger-Themen 8

Ähnliche Java Themen

Anzeige

Neue Themen


Oben