Array X-mal durchlaufen und dann N-mal durchlaufen

[slitec]

Hallo.

Mein Ziel war es die Lineare-Suche sowie die Binäre-Suche miteinander zu vergleichen. Hierzu habe ich ein Array zur Verfügung, welches mit Zahlen befüllt wird. Anschließend habe ich auch die Zeit gemessen, nur ist dies bei einer Messung nicht immer genau.

Mein Ziel ist es nun, 1000-mal durch die Liste zu gehen und eine Zahl zu suchen. Daraus dann einen Mittelwert berechnen (also Mittelwert der Suchzeit) um anschließend nochmals 30 mal diese verschiedenen Mittelwerte zusammen zu rechnen und einen endgültigen Mittelwert zu errechnen.
Kann mir da jemand behilflich sein ? Ich habe mir schon überlegt wie es vielleicht mit "for" gehen sollte aber komme nicht drauf.

Hier der Code für die Funktion :

public int suchzeitLinear(int suchzahl) {
        final long timeStart = System.currentTimeMillis();
        for (int i = 0; i < liste.length; i++) {
            if(liste[i] == suchzahl) {
                return i; //wenn gefunden wird beendet
            }
        }
        final long timeEnd = System.currentTimeMillis();
        long zeit = timeEnd - timeStart; //Dieser Wert soll für Mittelwert benutzt werden
        return -1; //wenn nicht gefunden
        
    }

Ganzer Code:

package A2;

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
    
    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 suchzeitLinear(int suchzahl) {
        final long timeStart = System.currentTimeMillis();
        for (int i = 0; i < liste.length; i++) {
            if(liste[i] == suchzahl) {
                return i; //wenn gefunden wird beendet
            }
        }
        final long timeEnd = System.currentTimeMillis();
        long zeit = timeEnd - timeStart; //Dieser Wert soll für Mittelwert benutzt werden
        return -1; //wenn nicht gefunden
        
    }
    
    
    
    
    public static void main(String[] args) {
        LineareSuche l1= new LineareSuche();
        l1.erzeugeZufallszahl(100, 200);
        l1.sortieren();
        l1.suchzeitLinear(10);
        
        
        l1.ausgabe();
    
    }
}

Vielen Dank schon mal für eure Hilfe.


Mit freundlichen Grüßen

 

[Zvoni]

Lineare Suche auf sortierte Liste wird gegen eine binäre Suche auf sortierte Liste am Ende immer verlieren.
Interessanter fände ich eher Lineare Suche auf unsortierte Liste gegen einen BST (wobei ich mir ziemlich sicher bin, der BST wird gewinnen)

 

[slitec]

Lineare Suche auf sortierte Liste wird gegen eine binäre Suche auf sortierte Liste am Ende immer verlieren.
Interessanter fände ich eher Lineare Suche auf unsortierte Liste gegen einen BST (wobei ich mir ziemlich sicher bin, der BST wird gewinnen)

Danke für deine Antwort. Dies ist mir auch bewusst, allerdings würde ich dies auch gerne beweisen. Deshalb hab ich auch danach gefragt.
Mir ist allerdings nicht klar wie ich die for-Schleife schreiben muss, damit 1000 mal eine Zahl aus der Liste gesucht wird und dann anschließend ein Mittelwert gebildet wird. Darauffolgend sollte dieser Mittelwert nochmals 30 mal berechnet werden.

Kann mir da vielleicht jemand behilflich sein?

 

[Technipion]

Mir ist allerdings nicht klar wie ich die for-Schleife schreiben muss, damit 1000 mal eine Zahl aus der Liste gesucht wird und dann anschließend ein Mittelwert gebildet wird. Darauffolgend sollte dieser Mittelwert nochmals 30 mal berechnet werden.

Ah, etwas konkretes. Dabei können wir gerne behilflich sein

import java.util.Random;


public class Mittelwertsbeispiel {

  Random zufallsGenerator = new Random();

  public Mittelwertsbeispiel() {  }

  public double erzeugeMesswert() {
    // führe eine Berechnung durch
    // wir tun hier allerdings nur so, indem wir eine Zufallszahl zurückgeben
    return zufallsGenerator.nextGaussian();
  }

  public double berechneMittelwert(int schritte) {
    // berechne Mittelwert aus <schritte> Versuchen

    double ergebnis = 0.0;

    for (int i = 0; i < schritte; i++) {
      ergebnis += erzeugeMesswert();
    }

    return ergebnis / schritte;
  }

  public double berechneGemitteltenMittelwert(int schritte1, int schritte2) {
    // berechne Mittelwert aus <schritte1> Mittelwerten, die aus
    // <schritte2> Werten berechnet wurden

    double ergebnis = 0.0;

    for (int i = 0; i < schritte1; i++) {
      ergebnis += berechneMittelwert(schritte2);
    }

    return ergebnis / schritte1;
  }

  public static void main(String[] args) {

    Mittelwertsbeispiel mb = new Mittelwertsbeispiel();
    double ergebnis = mb.berechneGemitteltenMittelwert(30, 1000);

    System.out.println("Ergebnis: " + ergebnis);
  }
}

Deinen ursprünglichen Code verstehe ich nicht. Warum z.B. gibt suchzeitLinear den Index des Elements in der Liste zurück? Das hat ja mit Zeitmessung überhaupt nichts zu tun...

Gruß Technipion

 

[Zvoni]

Stimme TP zu.
An deiner Stelle würde ich den 1000er-Lauf inkl. Zeitmessung innerhalb der Funktion machen (die "1000" vielleicht als Funktionsargument übergeben?), und den "ersten" Durchschnitt als Funktionsergebnis zurückgeben (Dazu brauchst du aber eine Variable, um die 1000 Zeitergebnisse aufzunehmen --> Array?)

Ausserhalb der Funktion (Also im Funktionsaufruf aus deiner "main") dann die äussere 30er-Schleife.
Du kannst ein Array 0 bis 29 definieren, um die Funktionsergebnisse deiner 1000er-Läufe aufzunehmen, und dann brauchste am Schluss nur noch den Durchschnitt aus den 30 Werten machen