Array X-mal durchlaufen und dann N-mal durchlaufen

Bitte aktiviere JavaScript!
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 :


Java:
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:

Java:
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
 
A

Anzeige


Vielleicht hilft dir dieser Kurs hier weiter: (hier klicken)
Könnte z.B. so aussehen:
Java:
import java.util.Random;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
@State(Scope.Benchmark)
@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@BenchmarkMode(Mode.AverageTime)
public class Bench {
    private static final Random random = new Random();
    private int[] liste = new int[1_000_000];
    private int suchzahl;
    @Setup(Level.Iteration)
    public void beforeIteration() {
        for (int i = 0; i < liste.length; i++)
            liste[i] = i;
    }
    @Setup(Level.Invocation)
    public void beforeInvocation() {
        suchzahl = random.nextInt(liste.length);
    }
    @Benchmark
    public int linearSearch() {
        for (int i = 0; i < liste.length; i++) {
            if (liste[i] == suchzahl) {
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) throws Exception {
        Options opt = new OptionsBuilder()
                .include(Bench.class.getSimpleName())
                .forks(1)
                .build();
        new Runner(opt).run();
    }
}
 
Könnte z.B. so aussehen:
Java:
import java.util.Random;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
@State(Scope.Benchmark)
@Warmup(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 5, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@BenchmarkMode(Mode.AverageTime)
public class Bench {
    private static final Random random = new Random();
    private int[] liste = new int[1_000_000];
    private int suchzahl;
    @Setup(Level.Iteration)
    public void beforeIteration() {
        for (int i = 0; i < liste.length; i++)
            liste[i] = i;
    }
    @Setup(Level.Invocation)
    public void beforeInvocation() {
        suchzahl = random.nextInt(liste.length);
    }
    @Benchmark
    public int linearSearch() {
        for (int i = 0; i < liste.length; i++) {
            if (liste[i] == suchzahl) {
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) throws Exception {
        Options opt = new OptionsBuilder()
                .include(Bench.class.getSimpleName())
                .forks(1)
                .build();
        new Runner(opt).run();
    }
}

Vielen Dank für den Code. Gibt es auch einen leichteren Weg dies zu realisieren ? Vielleicht mit Schleifen ? Für mich ist das noch etwas zu kompliziert.
 
Klar kannst Du mit Schleifen die Zeit ermitteln, das Ergebnis bringt Dir nur nicht allzu viel.

Hintergrund ist einerseits, dass Zeitmessungen in dem Bereich entsprechend fehlerbehaftet sind, andererseits - und das macht die Sache schwierig -, dass der Code sowohl zur Übersetzungszeit als auch zur Laufzeit optimiert wird. Selbst mit einem Framework wie jmh ist es alles andere als trivial, korrekte Benchmarks zu schreiben. Kurz: Microbenchmarking ist etwas, mit dem man sich intensiv beschäftigen muss, will man es richtig machen.

Andererseits muss man sagen, dass der Code von @httpdigest sehr viel einfacher ist als Deiner :)
 
Hintergrund ist einerseits, dass Zeitmessungen in dem Bereich entsprechend fehlerbehaftet sind
Kannst du Bereich nennen wo das nicht der Fall ist ?

Hintergrund:
Für meine Bachelor Arbeit entwickel ich eine Software die u. A. eine Methode beinhaltet die Entfernung zwischen 2 Standorten (Google Maps) berechnet.
Code:
public double getDistance(double lat1, double lon1, double lat2, double lon2) {
    Location startPoint = new Location("locationA");
    startPoint.setLatitude(lat1);
    startPoint.setLongitude(lon1);

    Location endPoint = new Location("locationB");
    endPoint.setLatitude(lat2);
    endPoint.setLongitude(lon2);
    double distance = startPoint.distanceTo(endPoint);

    return distance;
}
Hier wird die Luftdistanze ermittelt

Nun kann man aber auch die Fahrtdistanz mithilfe von Json Abfragen ermitteln

Code:
private void GetDistance(GeoPoint src, GeoPoint dest) {

    StringBuilder urlString = new StringBuilder();
    urlString.append("http://maps.googleapis.com/maps/api/directions/json?");
    urlString.append("origin=");//from
    urlString.append( Double.toString((double)src.getLatitudeE6() / 1E6));
    urlString.append(",");
    urlString.append( Double.toString((double)src.getLongitudeE6() / 1E6));
    urlString.append("&destination=");//to
    urlString.append( Double.toString((double)dest.getLatitudeE6() / 1E6));
    urlString.append(",");
    urlString.append( Double.toString((double)dest.getLongitudeE6() / 1E6));
    urlString.append("&mode=walking&sensor=true");
    Log.d("xxx","URL="+urlString.toString());

    // get the JSON And parse it to get the directions data.
    HttpURLConnection urlConnection= null;
    URL url = null;

    url = new URL(urlString.toString());
    urlConnection=(HttpURLConnection)url.openConnection();
    urlConnection.setRequestMethod("GET");
    urlConnection.setDoOutput(true);
    urlConnection.setDoInput(true);
    urlConnection.connect();

    InputStream inStream = urlConnection.getInputStream();
    BufferedReader bReader = new BufferedReader(new InputStreamReader(inStream));

    String temp, response = "";
    while((temp = bReader.readLine()) != null){
        //Parse data
        response += temp;
    }
    //Close the reader, stream & connection
    bReader.close();
    inStream.close();
    urlConnection.disconnect();

    //Sortout JSONresponse
    JSONObject object = (JSONObject) new JSONTokener(response).nextValue();
    JSONArray array = object.getJSONArray("routes");
        //Log.d("JSON","array: "+array.toString());

    //Routes is a combination of objects and arrays
    JSONObject routes = array.getJSONObject(0);
        //Log.d("JSON","routes: "+routes.toString());

    String summary = routes.getString("summary");
        //Log.d("JSON","summary: "+summary);

    JSONArray legs = routes.getJSONArray("legs");
        //Log.d("JSON","legs: "+legs.toString());

    JSONObject steps = legs.getJSONObject(0);
            //Log.d("JSON","steps: "+steps.toString());

    JSONObject distance = steps.getJSONObject("distance");
        //Log.d("JSON","distance: "+distance.toString());

            String sDistance = distance.getString("text");
            int iDistance = distance.getInt("value");

}
Eigetlich wäre Variante 2 für mein Vorhaben besseer geeignet, aber da über eine Schleife ca 100. 000 Abfragen stattfinden müssen und die Json Abfrage ziemlich lange dauert, muss ich auf Variante 1 zurückgreifen. Nun muss ich das natürlich begründen und wollte dazu die Zeiten der jeweiligen Abfragen ermitteln, womit ich dies dann begründen kann.[/code]
 
Eigetlich wäre Variante 2 für mein Vorhaben besseer geeignet, aber da über eine Schleife ca 100. 000 Abfragen stattfinden müssen und die Json Abfrage ziemlich lange dauert, muss ich auf Variante 1 zurückgreifen. Nun muss ich das natürlich begründen und wollte dazu die Zeiten der jeweiligen Abfragen ermitteln, womit ich dies dann begründen kann.
Grad in dem Fall kann man doch genug Begründungen liefern, ohne auf Benchmarks zurückgreifen zu müssen ;)
Ich kann natürlich nicht für deine Betreuer sprechen, aber mir wäre ein sinnvolle Erklärung deutlich lieber, als einfach nur ein Benchmark
 
Grad in dem Fall kann man doch genug Begründungen liefern, ohne auf Benchmarks zurückgreifen zu müssen ;)
Ich kann natürlich nicht für deine Betreuer sprechen, aber mir wäre ein sinnvolle Erklärung deutlich lieber, als einfach nur ein Benchmark
Ja villeicht hast du ja recht :D Allerdings wäre es so schon irgendwie "cooler" :cool::p
Wenn ich den direkten Vergleich hätte wie...
Var1 -> 1 ms
Var2 -> 1000 ms

Somit arbeitet Var1 bei gleichen Voraussetzungen (gleiche Systemumgebung) um 1000 % schneller......WOWWW!:eek:o_Oo_O
 
Zuletzt bearbeitet:
Kannst du Bereich nennen wo das nicht der Fall ist ?
Das Problem sind hier die sehr, sehr kurzen Zeitspannen. Der relative Fehler ist natürlich enorm hoch. Mal übertrieben: wenn Du Deinen Rechner schief anschaust, stimmt das Ergebnis schon um den Faktor 10 nicht mehr :)

Umgekehrt: überall dort, wo es um lange Zeiträume geht, spielen Dinge wie der Scheduler des Betriebssystems keine (eine untergeordnete) Rolle.

Im Prinzip ist es, wie bei der Ermittlung der Laufzeitkomplexität: wenn Du z. B. einen B-Baum für DB-Indizes nimmst, dann interessieren hier nur die Zugriffe auf das Speichermedium und die Suche im Hauptspeicher wird vernachlässigt.

Nun muss ich das natürlich begründen und wollte dazu die Zeiten der jeweiligen Abfragen ermitteln, womit ich dies dann begründen kann.
Dafür, dass eine Abfrage übers Netz millionenfach langsamer ist, als eine simple Luftlinienberechnung, braucht man doch wirklich keine Messung. Unabhängig davon kannst Du die Abfrage über das Netz mit sehr einfachen Methoden (System.currentTimeMillis) messen - da spielen Optimierungen der JVM oder der Scheduler des OS weniger eine Rolle. Natürlich wirst Du auch hier unterschiedliche Ergebnisse bekommen, aber Du könntest einen Mittelwert angeben. Allerdings: ich würde das nicht messen, da reichen schon theoretische Überlegungen (Datendurchsatz).
 
Dafür, dass eine Abfrage übers Netz millionenfach langsamer ist, als eine simple Luftlinienberechnung, braucht man doch wirklich keine Messung.
Oder tausendfach ? Oder auch nur hundertfach ? Villeicht braucht man ja gerade deswegen eine Messung ;-)
Aber gut, für meinen Anwendungsfall reicht es eigentlich zu wissen, dass das eine um einiges schneller ist als das andere. Die Dimension wird wohl nicht das entscheidende sein. Ich schätze ich werde es dann einfach anders begründen... :p
 
OK, das war zwar eigentlich nur als Spaß gedacht, aber wenn ich es mir recht überlege: im GSM-Netz kommt es einem nicht viel schneller vor und immer ist auch das kabelgebundene Netz nicht wirklich schnell.

Was anderes: berechnest Du die Luftlinie per Pythagoras oder berücksichtigst Du die Krümmung der Erdoberfläche?
 
berechnest Du die Luftlinie per Pythagoras oder berücksichtigst Du die Krümmung der Erdoberfläche?
Habe mal nachgeschaut, als Berechnungsgrundlage dient wohl die Krümmung der Erde.

Die distanceTo() Methode (aus Var1) ist wie folgt beschrieben
Returns the approximate distance in meters between this location and the given location. Distance is defined using the WGS84 ellipsoid.
->https://de.wikipedia.org/wiki/World_Geodetic_System_1984
 
Java:
long start = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {
    suche(suchzahl);
}
long millis = System.currentTimeMillis() - start;
double mittelwert = millis / 1000.0;
 
Java:
long start = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {
    suche(suchzahl);
}
long millis = System.currentTimeMillis() - start;
double mittelwert = millis / 1000.0;
Ich habe mir gedacht, dass die Zeit nur immer bei einem Suchschritt gemessen wird und diese dann addiert. Habe mal ein Code geschrieben der leider nicht funktioniert:

Java:
    public int suchzeitLinear2() {
        
        int zeit30=0; //Zeit für 30
        for (int x=0; x<30;x++) {
        int    zeit1000=0; // Zeit für 1000
        for (int j=0; j<1000;j++ ) {
            
            int suchzahl = liste[zufall.nextInt(liste.length)]; //legt eine zufällige Suchzahl im Array fest
            final long timeStart = System.nanoTime();
            for (int i = 0; i < liste.length; i++){
                if(liste[i] == suchzahl){
                    final long timeEnd = System.nanoTime();
                    zeit = timeEnd - timeStart; //Dieser Wert soll für Mittelwert benutzt werden
                    System.out.println("Suchzeit: "+zeit+ " "+ suchzahl);
                    return i; //wenn gefunden wird beendet
                }
            }
                    
            zeit1000 += zeit;
            return -1; //wenn nicht gefunden
            
        }
        zeit30 += zeit1000 /1000;
        }
        
        int zeitFinal=zeit30/30;
        return zeitFinal;
    }
Nach der innersten Schleife " for (int i = 0; i < liste.length; i++)" wird hier allerdings abgebrochen. So in etwa habe ich es mir vorstellt. Kann mir jemand sagen ob mein Code korrekt ist? Wenn nicht, woran könnte es liegen?

Danke
 
Habe mal ein Code geschrieben der leider nicht funktioniert:
Kann mir jemand sagen ob mein Code korrekt ist? Wenn nicht, woran könnte es liegen?
Wieso sollte der Code korrekt sein, wenn er nicht funktioniert?!? Trenn doch einfach mal die Suchfunktion von der Zeitmessung (wie in der Skizze von mir), das macht die Sache schon wesentlich einfacher. Abgesehen davon ist es keine gute Idee ein long auf ein int zu addieren.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben