Frage bei Zufallszahlen

fanbjs

Hi Leute,

Ich brauche Hilfe.

Ich habe ein Array: DeletSet. Es besteht aus 10000 Einträgen.

Die Einträge sehen so aus:

typedef struct freq {

   int instr; 
   int instr; 

}

Ich möchte aus disem Array jedesmal eine andere Zahl zufälligerweise auslesen.

for ( i =0; i <100; i++)
{  
    srand((unsigned) time(NULL)); 
    DeletSet[t = rand()%10000].instr;

    if (DeletSet[t].m !=-1)
    {
	val =DeletSet[t].instr; 
	DeletSet[t].m = -1;
        printf ("%u\n", val)
    }	
    else {
     i--;
     continue;
    }
}

Wenn Ich meine Funktion so schreibe, dauert es ziemlich lange bis er diese 100 Schritte durchläuft.

Wie kann Ich besser die Funktion implementieren, damit eine Zahl nur einmal ausgelesen wird.

Im Voraus Vielen Dank

Daniel E.

Bitte copy&paste machen. Die Struktur sieht zB etwas wirr aus.
srand muß prinzipbedingt nur ein mal pro Programmablauf gestartet werden, also raus damit aus der Schleife (das ist der eigentliche Fehler).
Statt 'DeletSet[t = rand()%10000].instr;' kann auch einfach 't = rand()%10000;' schreiben ...

Ansonsten ist das Vorgehen wohl okay, wenn nur 1% der Zahlen gezogen werden.

fanbjs

Vielen Vielen Dank,

Das hat mir sehr geholfen.

Viele Grüsse

Lena

tim_g

Sicherer und meiner Meinung nach eleganter ist das folgende Vorgehen:

Fuellen eines Hilfsstructs mit 10000 Eintraegen fortlaufend von 1-10000
Durchlaufen des Hilfsstruct, wobei der Inhalt des aktuellen Laufindexes mit einem Zufallsindex (rand()%10000) vertauscht wird.
Kopieren der ersten 100 Eintraege des Hilfsstructs in das eigentliche struct.

Vorteil dieser Methode ist, dass auch bei mehr als 100 Eintraegen tatsaechlich jede Zahl hoechstens ein Mal vorkommt.

P.S.: laut 'man 3 rand' bzw. den 'Numerical Recipes in C' sollte man nicht die unteren bits benutzen, die rand erzeugt, sondern die oberen.

Mario Sandler

Das hab ich auch schon gehört mit den unteren bits.
Ich ahb ehrlcih gesagt nei verstanden was das bedeuten soll.
Wie soll ich den die unteren bits verwenden?
Was hat diese ganze zufallssache mit bits zu tun.
Vielleicht liegt die Lösung ja intern, weiß einer wie so ein rand() funktioniert?
Geht das mit nem speziellen algorithmus?

tim_g

Wahrscheinlich arbeitest Du unter Windows, sonst koenntest Du einfach 'man 3 rand' eingeben und nachlesen. Der code, um die oberen Bits zu nutzen, lautet wie folgt:

int index;
index = (int)(10000.0*rand()/(RAND_MAX+1.0));

Weshalb man das tun soll, ist in Kapitel 7 der 'recipes'. Um es vollstaendig zu verstehen, sollte man Zahlentheorie koennen sowie die Definition von Zufallszahlen verstehen. Beides ist bei mir nicht der Fall, so dass ich Dich mit der Antwort leider alleine lassen muss.

Es wird immerhin erwaehnt, dass die unteren bits bei dem Algorithmus, der in den 'recipes' beschrieben wird, weniger zufaellig sind als die hoeheren.

Mario Sandler

@tim_g
Schau mal in meine Signatur

man hatte einfach keine antwort auf meine Frage nach der internen Arbeitsweise von rand() und warum die unteren bits weniger zufällig sind.

tim_g

@Storm.Xapek.de
In der man-page steht der Verweis auf Kapitel 7 der Recipes, die es online gibt. Dort steht das recht gut beschrieben, auch, wie rand() i.d.R. implementiert wird (haengt vom Compiler ab).

Daniel E.

tim_g schrieb:

Es wird immerhin erwaehnt, dass die unteren bits bei dem Algorithmus, der in den 'recipes' beschrieben wird, weniger zufaellig sind als die hoeheren.

Das kann so sein, muß aber nicht. Siehe, zB man 3 rand ;):
The versions of rand() and srand() in the Linux C Library use the same
random number generator as random() and srandom(), so the lower-order
bits should be as random as the higher-order bits.

Trotzdem kann es natürlich immer passieren, daß man mit der Modulo-Methode bestimmte Zahlen benachteiligt.

Beispiel: ein fiktives rand liefert gleichverteilte Zufallszahlen zwischen 0 und 10, ich verwende es wie folgt: zufall=rand()%3. Was passiert also:

0 => 0
1 => 1
2 => 2
3 => 0
4 => 1
5 => 2
6 => 0
7 => 1
8 => 2
9 => 0
10 => 1

Also kommt die 0 und die 1 hier mit 4/11 Wahrscheinlichkeit, die 2 nur mit 3/11 ist systematisch benachteiligt. Wenn's wirklich auf eine im statistischen Sinne gute Verteilung ankommt (im Gegensatz zu "sieht irgendwie zufällig aus"), dann macht man das nicht einfach so, sondern denkt etwas mehr darüber nach, aber hier schien mir das nicht gefragt zu sein. Darum reicht das mE genau so, wie das Die-Schleife-nochmal-durchnudel-Verfahren um doppelte Zufallszahlen zu vermeiden.

tim_g

Wenn ich richtig gerechnet habe, ist die Wahrscheinlichkeit, dass von 100 Zahlen, die zwischen 1 und 10000 liegen, alle unterschiedlich sind, etwa 60%. Das waere mir zu wenig.

Daniel E.

tim_g schrieb:

Wenn ich richtig gerechnet habe, ist die Wahrscheinlichkeit, dass von 100 Zahlen, die zwischen 1 und 10000 liegen, alle unterschiedlich sind, etwa 60%. Das waere mir zu wenig.

Ohne nachgerechnet zu haben: das natürlich aus der Kategorie "so trickst man mit Statistik".

Die Wahrscheinlichkeit, daß alle unterschiedlich sind, ist 60%, sagst Du. Schön. Die entscheidendere Frage ist aber: wie viele sind statistisch doppelt? Weil: es reicht ja schon eine doppelte Zahl um das Kriterium "alle unterschiedlich" zu zerstören und dann muß ich die Schleife statt 100 mal 101 mal durchlaufen. Selbst wenn man 110 mal durchlaufen muß (10% !), dürfte sich das auf das Laufzeitverhalten kaum durchschlagen, besonders da das idR ein Teil deines Programmes ist, das nur ein mal pro Initialisierung (von was auch immer) durchgeführt wird.

Andererseits: da dein "Hilfsarray" hier anscheinend praktisch eh schon existiert (die Nutzdaten sind nur ein int, also...), kann man deinen Algorithmus (sogar unter der Einsparung der Hilfsvariablen m) bequem implementieren.

Ob's das der OP wert ist, muß sie selber aber wissen, vielleicht kommts darauf ja wirklich nicht an ...