bestes Intervall

[El Hadji]

Servus Community,
Ich bin gerade am Lernen für eine Prüfung und versuche mich an einem alten Prüfungsbeispiel und komme nicht weiter.
Es handelt sich um eine Klasse mit einem parameterlosen Konstruktor und ht jediglich die Methode:
public double findeBestesIntervall(double [] punkte, double weite)

Die Methode soll einen Wert zurückgeben in dem am meisten Punkte des Arrays im Intervall (sprich in der weite enthalten sind).
Soweit so gut. Hier meine Ansätze:

import java.util.*;

public class DenseIntervals
{
 
    public DenseIntervals()
    {
      
    }

 
    public double findeBestesIntervall(Double [] punkte, double weite)

    {
       
        Arrays.sort(punkte);
       
       List <Double> neu = Arrays.asList(punkte);
       ArrayList<Double> sortiert = new ArrayList<Double>(neu);
     
     
      
       for(int i = 0; i < sortiert.size(); i++)
       {
           int distanz = 0;
           int count = 1;
         
          
           for (int j = i+1; j  < sortiert.size(); j++)
           {
            
           }
        
        }
      
    }
}

Also als erstes sortiere ich meine Array und überschreibe sie in eine ArrayList weil ich mir dann leichter tue. Danach gehe ich mit einer for-Schleife den ersten Wert durch und erhöhe in der 2ten for-Schleife i um 1 damit nicht die Distanz zum selben Punkt genommen wird.

Jetzt hänge ich an der if-Bedingung. Ich müsste einen lokalen Zähler einfügen und vergleichen nach wievielen Punkten das Intervall überschritten wird.
Ich wäre euch sehr dankbar wenn ihr mir einen Denkanstoß geben könntet.

Wünsche euch noch einen schönen Abend
und vielen Dank im voraus El Hadji

 

[Xyz1]

Och Mensch, das gibt's doch nicht... hier geht's direkt zur Lösung: http://www.java-forum.org/thema/hilfe-bei-java-hasuebung.174949/#post-1104774 (doppelte Frage gestellt hier, Doppelpost)

 

[El Hadji]

Sorry, ich weiß leider die Suchfunktion nicht. Aber der andere Post ist nicht von mir^^)
Dann schreib ich im anderen Thread weiter und der hier kann zu, dankesehr

 

[Xyz1]

Wobei ich die main dann so geschrieben hätte:

    public static void main(String[] args) {
        Random ran = new Random();
        double[] array = Arrays.stream(new double[6]).map((d) -> ran.nextDouble()).toArray();
        System.out.println(Arrays.toString(Arrays.stream(array).map((d) -> (int) (d * 100) / 100.0).toArray()));

        DenseIntervals di = new DenseIntervals();
        double res = di.findDense(array, 0.5);
        System.out.println("res = " + res);
    }

Aber das kann ja jeder abändern, wie er möchte.

Beispiel:
[0.48, 0.84, 0.45, 0.14, 0.93, 0.8]
res = 0.4507048359092768

Im Intervall [0.45, 0.95] liegen meisten Punkte, nämlich...

 

[Xyz1]

Sorry, ich weiß leider die Suchfunktion nicht. Aber der andere Post ist nicht von mir^^)
Dann schreib ich im anderen Thread weiter und der hier kann zu, dankesehr

Kein problem, bei < 30 Beiträgen sei dir verziehen

 

[El Hadji]

ok nur eine blöde Frage am Rande, was amcht es einen Unterschied ob ich Double [] oder double [] schreibe?

 

[Ruzmanz]

http://www.java-forum.org/thema/unterschied-zwischen-double-und-double.155155/

Du solltest übrigens an deiner Lösung weiterarbeiten. Sie könnte um Welten besser sein als die verlinkte Lösung. Dass du das Array zuerst sortiert hast, ist korrekt. Dadurch reduzierst du dein d-dimensionales Problem zu einem (d-1)-dimensionalen Problem, welches du effizienter lösen kannst

 

[VfL_Freak]

Moin,

Sorry, ich weiß leider die Suchfunktion nicht

oben rechts in der hellblauen Leiste ist ein weißes Feld in dem "Suche..." steht .....

Gruß Klaus

 

[Xyz1]

Ich schaue immer Neue Beiträge -> Themen mit aktuellen Beiträgen ,
und wenn etwas Interessantes dabei ist, Antworte ich immer gleich .

Dass du das Array zuerst sortiert hast, ist korrekt. Dadurch reduzierst du dein d-dimensionales Problem zu einem (d-1)-dimensionalen Problem,

Wirklich? Ich hab dann immer noch eine Laufzeit von n*n/2 , also immer noch zwei geschachtelte Schleifen , nicht linear

 

[Xyz1]

Nochmal mit Sortierung:

class DenseIntervals {
    DenseIntervals() {
    }
    public double findDense(double[] points, double width) {
        Arrays.sort(points);
        double res = Double.NaN;
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            int tmp = 0;
            for (int j = i; j < points.length; j++) {
                if (points[i] <= points[j] && points[j] <= points[i] + width) { // schlanker
                    tmp++;
                } // else: abbruch?
            }
            if (tmp > max) {
                res = points[i];
                max = tmp;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Random ran = new Random();
        double[] array = ran.doubles(6).toArray();

        DenseIntervals di = new DenseIntervals();
        double res = di.findDense(array, 0.5);

        System.out.println(Arrays.toString(Arrays.stream(array).map((d) -> (int) (d * 100) / 100.0).toArray()));
        System.out.println("res = " + res);
    }
}

[0.02, 0.03, 0.58, 0.71, 0.74, 0.95]
res = 0.58

if-else- lässt sich vielleicht anders schreiben, auch i < points.length usw.
Aber wie ist das gemeint, mit nur einer Schleife?

(Und, mal wieder dumm gefragt,: Kann man aus Strings keinen Stream machen?)

 

[mrBrown]

(Und, mal wieder dumm gefragt,: Kann man aus Strings keinen Stream machen?)

String.chars() oder String.codePoints()

 

[mrBrown]

if-else- lässt sich vielleicht anders schreiben, auch i < points.length usw.
Aber wie ist das gemeint, mit nur einer Schleife?

Wenn ich mich grad nicht irre, kann man statt j=i direkt j=i+max nehmen und im else breaken, die innere Schleife läuft dann maximal points.length statt points.length^2 mal, s

 

[Xyz1]

Das wäre eine Möglichkeit, um hoffentlich das quadratische zu vermeiden,
aber letztlich müsste man das mal mit sehr großen Datenmengen testen,
welcher Asymptote es sich nähert...

 

[mrBrown]

O(n) ^^
Das Sortieren braucht mehr Zeit, also bleibt nur das übrig.

Man lässt im Prinzip ein Fenster über das Array laufen, und von dem muss man nur das letzte Element prüfen (da sortiert). Entweder das passt ins Intervall, dann Position merken und um eins vergrößern und sonst um eins verschieben.
Fenster startet mit Länge 2, und kann (n-2) mal verschoben oder vergrößert werden (jedes vergrößern führt zu einmal weniger verschieben und andersrum), sonst reicht's übers Array hinaus.

Dichte ist dann der Wert an der gemerkten Position.

 

[Xyz1]

Alles klar, ich hab jetzt 1 Std. "intensiv" getestet, das kam raus:

class DenseIntervals {

    DenseIntervals() {
    }

    public double findDense1(double[] points, double width) {
        double res = Double.NaN;
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            int tmp = 0;
            for (int j = 0; j < points.length; j++) {
                if (points[i] <= points[j] && points[j] <= points[i] + width) {
                    tmp++;
                }
            }
            if (tmp > max || (tmp == max && points[i] < res)) {
                res = points[i];
                max = tmp;
            }
        }
        return res;
    }

    public double findDense2(double[] points, double width) {
        Arrays.sort(points);
        double res = Double.NaN;
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            int tmp = max;
            for (int j = i + max; j < points.length; j++) {
                if (points[j] <= points[i] + width) {
                    tmp++;
                } else {
                    break;
                }
            }
            if (tmp > max) {
                // System.out.println("found: " + points[i] + " with: " + tmp);
                res = points[i];
                max = tmp;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Random ran = new Random();
        double[] array = ran.doubles(100000).toArray();

        DenseIntervals di = new DenseIntervals();

        long t1 = System.currentTimeMillis();
        double res = di.findDense1(array, 1.0 / 3.0);
        long t2 = System.currentTimeMillis();
        System.out.println("res = " + res);
        long t3 = System.currentTimeMillis();
        res = di.findDense2(array, 1.0 / 3.0);
        long t4 = System.currentTimeMillis();
        System.out.println("res = " + res);

        System.out.println(t2 - t1);
        System.out.println(t4 - t3);
        System.out.println(100.0 / (t2 - t1) * (t4 - t3));
    }
}

res = 0.47...
res = 0.47...
74349
31
0.04169524808672612

findDense1 hat quadratisches Wachstum (jetzt mal echt ),
findDense2 hat logarithmisch-lineares Wachstum .

findDense2 ist bei mir 2398...mal schneller als findDense1...

Zudem muss, beinhalte das Intervall 33.001 Elemente, findDense1 den Punkt zurückgeben, der der kleinste ist, dessen Intervall 33.001 Elemente beinhaltet, nicht, der im unsortierten Array der erste ist.

Also, ist das Intervall gleich-lang, nicht der erste, sondern der kleinste.

 

[Ruzmanz]

Eigentlich prüft man das nicht mit der Systemzeit.

Die Anweisung durchläufst du in n.
for (int i = 0; i < points.length; i++)

Diese Anweisung braucht im ersten Durchlauf n, im zweiten Durchlauf n-1, im dritten Durchlauf n-2 ... Also n + n-1 + n-2 + ... + n-n => Das müssten n*(n+1)/2 sein.
for (int j = i + max; j < points.length; j++)

Ein optimaler Algorithmus könnte ungefähr so aussehen:
(Habe es nicht großartig getestet, evtl. sind ein paar Fehler drinnen)

Die äußere Schleife ist ziemlich einfach. Auf points wird n-Mal zugegriffen. Die innere Schleife sieht ein bisschen komplexer aus. Aber wenn du dir nur j anguckst, dann wirst du feststellen, dass j im gesamten Programmdurchlauf wie i nur hochgezählt wird.

import java.util.Arrays;

public class Dent {
   public static void main(String[] args) {
     double[] points = {0.66, 0.67, 0.8, 0.99, 1.0, 1.1, 1.11, 1.12, 1.13};
     double width = 0.33;
     
     if(points.length < 0) {
       return;
     }
     
     Arrays.sort(points); // O(n*log(n))
     
     int j = 1;
     double x = Double.NaN;
     int streak = 0;
     double nextValue = points[j];
     
     for(int i = 0; i < points.length; i++) { // insgesamt O(2n) = O(n)
       double fromPoint = points[i];
       double range = fromPoint  + width;
       
       while(range >= nextValue && j+1 < points.length) {
         nextValue = points[++j];
       }
       
       if(streak < j-i) {
         x = fromPoint;
         streak = j-i;
       }
     }
     
     System.out.println(x);
   }
}

 

[Xyz1]

Wie es letztlich genau schaut, ist egal. Auch Schleife in Schleife, auch j, das in der inneren hochgezählt wird usw.

Eigentlich prüft man das nicht mit der Systemzeit.

Jep, aber jegliches (Micro-)Benchmark-Kit(/-Tool) will bei mir nicht laufen (zur Zeit).