3. Funktion zur zufälligen Auswahl von Elementen effizienter gestalten

Funktion zur zufälligen Auswahl von Elementen effizienter gestalten

  • N

    Hallo,

    ich habe folgende Funktion, wobei random(n) eine zufällige Zahl zwischen 0 und n-1 liefert:

    int rselect(int c,int p)
{
 int s=0;
 for (int i=0;i<c;++i)if (random(100)<p)s++;
 return s;
}

    Meine Frage ist nun, kann man das effizienter machen? Wenn c sehr hoch ist, dauert das ganze viel zu lange.
    Gerade wenn ich mir mal die Funktionswerteverteilung von ein paar Millionen Aufrufen ansehe, dann sehe ich, dass der Graph seinen Höhepunkt bei c*p/100 hat und nach beiden Seiten desto steiler abfällt, je kleiner p ist, was mich vermuten lässt, dass die Mathematik da eine bessere Lösung bereithält.
    Könnte mir jemand einen Denkanstoß geben?

    Danke im voraus,
    Nanyuki

    0
  • B

    Tjo, dann waer's nicht schlecht wenn du uns sagen wuerdest, was die Funktion denn machen sollte. Momentan simulierst du im Prinzip die Binomialverteilung, und dafuer gibts auch andere Formeln (siehe Wikipedia).

    0
  • N

    Ich brauche im Prinzip nur eine allgemeine Funktion, die aus einer Menge von c Elementen jedes mit einer Wahrscheinlichkeit p auswählen kann. Da alle Elemente gleicher Art sind, brauche ich letztendlich nur die Anzahl der ausgewählten Elemente zu wissen.
    Aber Binomialverteilung scheint genau das richtige Stichwort zu sein, danke.
    Das schau ich mir mal genauer an.

    0
  • B

    Nanyuki schrieb:

    Da alle Elemente gleicher Art sind, brauche ich letztendlich nur die Anzahl der ausgewählten Elemente zu wissen.

    dann koennte ja ein einzelner Aufruf von random() reichen:

    int anzahl_ausgewaehlte_elemente = ANZAHL_ELEMENTE * random(100) / 100.f;

    Sagt dir dann, wieviel Elemente du auswaehlst.

    Allerdings ist der Wert normal- statt binomial verteilt. Wenn du eine binomiale Verteilung haben moechtest, kannst ganz einfach die Formel nehmen, die auf Wikipedia steht. Ansonsten hat boost einen Generator, der binomial verteile Zufallszahlen liefert: http://www.boost.org/libs/random/index.html (unter "bernoulli distribuition")

    0
Anmelden zum Antworten