Array erzeugen mit verschiedener Verteilung

slitec

Mitglied
Hallo.

Wie kann man ein Array erzeugen, sodass die Verteilung unterschiedlich ist und gewisse Zahlen (z.B. die 0 und die 14) immer vorhanden sind?

Bis jetzt habe ich den Array so erstellt:

Java:
private void erzeugenVerteilt()
        {
           for (int i = 0; i < liste.length; i++) {
              liste[i] = i*10 + zufall.nextInt(10);
           }
    
        }

Ich möchte gerne die Binäre-Suche und die Interpolations-Suche mit zwecks der Laufzeit vergleichen. Hierzu erstelle ich gleich verteilte Daten also 0,1,2,3...99 und nicht gleich verteilte Daten also z.B. 0,4,6,7,14.... .
Da ich hierzu eine X-beliege Zahl suchen möchte, muss es eine Zahl sein, die immer generiert wird wenn ich auch nicht gleicht verteilte Daten erzeuge. Hat da jemand von euch eine Idee wie ich dies lösen kann?

Den kompletten Code findet ihr hier:

Java:
package A1;
import java.util.Random;


 public class BinaereSuche
{
     int[] liste; //Array wird definiert als "liste"
     Random zufall = new Random();    // wird erzeugt für Klasse erzeugenUnsortiert()
     int n = 0;      // Anzahl der Suchschritte
     int suchzahl; //Dies ist die gesuchte Zahl
     int links; // linker Index
     int rechts; // rechter Index         
    
     public BinaereSuche(int plätze) {
        
         liste = new int [plätze];
         //Anzahl an Plätze wird übergeben
     }
    
     // --> Sortiert
     public void erzeugeSortiert() {
            for (int i=0; i<liste.length; i++) {
            //100 Zahlen werden erzeugt
                liste[i] = i;   
            //Enthält zahlen von 0-99 --> 100 Zahlen
            }
             links = liste[0];
             rechts = liste[99];
        }
    
    // --> Sortiert unterschiedlich verteilt
        private void erzeugenVerteilt()
        {
           for (int i = 0; i < liste.length; i++) {
              liste[i] = i*10 + zufall.nextInt(10);
           }
           links = liste[0];
           rechts = liste[99];
        }
    
     // --> Unsortiert
     public void erzeugenUnsortiert() {
            for (int i=0; i<liste.length; i++){
                int z1 = zufall.nextInt(100);
                for (int z = 0; z < i; z++) {
                    if (z1 == liste[z]) {
                        i--;
                        z=100;
                    }else{
                        liste[i] = z1;
                    }
                }
            }
        }
    
    
        public void ausgabe() {
            for (int i=0; i<liste.length; i++) {
                System.out.println("Zahl: "+ liste[i] + " || Index: " + i);
            }
        }
        
                                    //!!! Suchzahl muss also in Array vorhanden sein ??? FRAGE?
        public int suchzeitBinaer(int suchzahl) {
            
            int mitte;
            //rechts = liste.length-1; // z.B. 0-99 Zahlen --> 99/2 = 49
            
            do {
                
                if (suchzahl >= liste.length) {
                    System.out.println("Suchzahl nicht enthalten");
                    return -1;
                }
                // Wenn Zahl größer als 99 in diesem Fall
                
                mitte = (links+rechts)/2; // Mitte wird gebildet
                n++;
                System.out.println(mitte+" == Mitte         | Schritt:" +n);
                
                
                if (liste[mitte] == suchzahl) {
                    System.out.println("Suchzahl: " + mitte);
                    return mitte;
                }
                if (liste[mitte] > suchzahl) {
                    rechts = mitte-1;
                    n++;
                    System.out.println(rechts + " =="+" Rechts = Mitte -1"+" | Schritt:" +n );
                }
                if (liste[mitte] < suchzahl) {
                    links = mitte+1;
                    n++;
                    System.out.println(links + " =="+" Links = Mitte +1"+"  | Schritt:" +n );
                }
                
            } while (links <= rechts && liste[mitte] != suchzahl);
            System.out.println("Zahl nicht gefunden");
            return -1;
            
            }
        
        public void ausgabe1() {
            for (int i=0; i<liste.length; i++) {
                System.out.println(liste[i] + " || Schritt: " + (i+1));
            }
        }
        
        
                
        
    
    public static void main(String[] args)
    {
    
    BinaereSuche b1 = new BinaereSuche(100);
    //b1.erzeugeSortiert();
    b1.erzeugenVerteilt();
    //b1.erzeugenUnsortiert();
    //b1.ausgabe();
    b1.suchzeitBinaer(12);
    
    }
}
 

Technipion

Erfahrenes Mitglied
Du möchtest also die 14 immer in deinem Array haben?

Dann erstelle doch einfach ganz normal deine Arrays und füge die 14 zum Schluss an einer zufälligen Position im Array ein. Würde auch mit mehreren Zahlen (0, 14, etc.) gehen.

Alternativ kannst du natürlich auch maßgeschneiderte Arrays erzeugen und einfach shuffeln.

Gruß Technipion
 

slitec

Mitglied
Danke für deine Antwort.

Das Problem ist, wenn ich die Methode erzeugenVerteilt() aufrufe, dann werden ja zufällige Zahlen zwischen 0- 999 erzeugt.
Wenn ich dann z.B. die Methode suchzeitBinaer(14) aufrufe, bekomme ich ab und zu eine Fehlermeldung, da die Zahl 14 nicht immer erzeugt wird.

Gibt es vielleicht deshalb eine Möglichkeit, anders verteilte Daten zu erzeugen, die immer die selben sind ? Also z.B. immer (0, 4, 6, 7, 12, 16, 17, 24...).
 

Technipion

Erfahrenes Mitglied
Du kannst ausnutzen, dass dein Zufallsgenerator deterministisch ist. Einfach beim Erzeugen einen Seed mit angeben:
Java:
Random zufall = new Random(12345);
// In diesem Fall ist der Seed 12345
// Es kann aber eine beliebige long sein

Der Zufallsgenerator wird jetzt nach jedem Programmstart die gleiche Reihenfolge von (Pseudo-)Zufallszahlen ausspucken. Falls du mehrere Durchläuft mit gleichem Seed machen willst, kannst du ihn auch im Nachhinein setzen:
Java:
zufall.setSeed(12345);
// Der Seed wird auf 12345 zurückgesetzt

Falls du Zufallszahlen mit anderen Verteilungen erzeugen willst, lohnt sich ein Blick in die Dokumentation: Random (Java Platform SE 8 )

Statt nextInt() könntest du z.B. nextGaussian() benutzen. Prinzipiell gibt es aber verschiedene Methoden um beliebige Verteilungen aus [0, 1) zu erzeugen, also falls du was spezielles brauchst einfach melden.

Gruß Technipion
 

Bratkartoffel

gebratene Kartoffel
Premium-User
Gibt es vielleicht deshalb eine Möglichkeit, anders verteilte Daten zu erzeugen, die immer die selben sind ? Also z.B. immer (0, 4, 6, 7, 12, 16, 17, 24...).
Hi,

am einfachsten wäre dies, wenn du ein fixes Array erzeugst und dieses dann mischst: Random shuffling of an array

Java:
int[] liste = new int[] { 0, 4, 6, 7, 12, 16, 17, 24, 33, 55, 61 };
shuffleArray(liste);

Grüsse,
BK
 

Neue Beiträge