doppelte srand() initialisierung

[noreaga]

Hallo!
Ich habe ein kleines Problem beim erzeugen von Zufallszahlen. Für mein Praktikum in Algorithmen und Datenstrukturen ist ein Tool zur Laufzeitmessung verschiedener Sortieralgorithmen zu schreiben. Dazu benötige ich ein Array mit zufälligen Werten. Dazu verwende ich folgenden Code:

const int * generator::init() {

	srand(time(NULL));
	unsigned int factor = (rand() % 100);
	
	srand(clock());
	for(int p=0; p < this->n; p++) {
		this->walk_ptr[p] =  ((rand() * factor) % this->upper_border);

	}
	return this->ptr;
}

Da das Array sowohl einzeln als auch in schleifen neu initialisiert werden soll, habe ich mich entschieden, den Zufallszahlengenerator doppelt zu initialisieren. Einmal abhängig von der Zeit mit srand(time(NULL)) um für einzelne aufrufe zu verschiedenen Zeitpunkten jeweils ein neues Feld zu haben und einmal mit srand(clock()) um andere Zahlen zu bekommen wenn die funktion init() in schleife aufgerufen wird. Leider werden beim Aufruf in schleife trotzdem immer die selben Zahlen geliefert. Weis vielleicht jemand, ob der Zufallszahlengenerator nur 1 mal initialisiert werden kann? Oder hat jemand einen anderen Vorschlag für mein Problem?

P.S. ich weis, dass die Zahlen durch die modulo operation statistisch nicht mehr gleichverteilt sind... das kann man hier mal vernachlässigen

 

[der_Kay]

Hallo,

rand() ist meist ein (schlechter) linearer Kongruenzgenerator, d. h. zu einem festen Startwert (via srand()) wird immer der gleiche Zahlenstrom erzeugt, wie man aus der Formel leicht sieht. Es ist also überflüssig, den Generator zweimal zu initialisieren, da nur zwischen zwei im Voraus bestimmten Zahlenströmen hin- un hergeschaltet wird.

Es ist im übrigen für Debugging-Zwecke durchaus sinnvoll, einen festen Startwert zu wählen.

Was Dein Problem angeht, das hat lustige Ursachen:

1.) time() gibt zeit in Sekunden zurück, ein elend langer Zeitraum. Je nach dem, wie schnell du sortierst, wird die init()-Funktion vielleicht zig mal pro Sekunde aufgerufen. Klar, dass dann der Startwert immer derselbe ist.

2.) Bei clock() schlägt das casten nach unsigned int fehl, Resultat immer 0. Genaues hab ich noch nicht gefunden.

Mach also programmweit nur einen einzigen srand()-Aufruf.

p.s.:
Sortieralgorithmen vergleicht man, indem man die Größenordungen ihrer Laufzeiten für best, average und worst-case berechnet.

 

[rikola]

clock() gibt die Zeit zurueck, die die CPU bisher fuer Dein Programm aufgebracht hat. Der aendert sich an dieser Stelle nur, wenn Du am Code etwas aenderst oder das Programm auf einer schnelleren/ langsameren CPU laufen laesst. Sonst ist der Wert, den clock() dort zurueckgibt, immer der gleiche.

Du solltest srand einmal in main() aufrufen. Die Idee eines Zufallsgenerators ist, dass dann auch wirklich von rand() stets 'zufaellige' Zahlen zurueckgegeben werden.

 

[noreaga]

Danke für die Antworten!
Ich hatte wohl einen kleinen Denkfehler, jetzt funktionierts jedenfalls so wie ich mir das vorgestellt habe.

Ich hätte noch ne kleine Frage, die etwas vom Thema abweicht, aber um nicht noch einen Thread aufmachen zu müssen, stell ich die mal hier:

Um die Laufzeiten der Algorithmen zu visualisieren (es geht bei uns eigtl. nur um die Anzahl der Zuweisungen, Vertauschungen und Vergleiche) möchte ich auf eine möglichst einfache lib zurückgreifen. Es würde für mich die libGD in Frage kommen, da ich das Paket später auf windoze portieren soll und ich mit ihr schon unter PHP gearbeitet habe. Kennt vielleicht jemand eine art Framework um damit simple 2D Graphen schnell zeichnen zu lassen? Ansonsten muss ich mir wohl die Sachen selber schreiben, was auch nicht so viel Aufwand bedeuten würde, aber man spart wo man kann.

Danke für die Antworten !