Mersenne Twister als RNG für random_shuffle

railrun

Hallo,

in der CPP-Referenz steht, dass man einen "eigenen" RNG als Zufallsgenerator verwenden kann. http://www.cplusplus.com/reference/algorithm/random_shuffle/

template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
                        RandomNumberGenerator& rand );

Nun wollte ich von http://www-personal.umich.edu/~wagnerr/MersenneTwister.html die Funktion verwenden. Ich hab einen Vector von der Größe unsigned long int, welcher Strings enthält.

Wie kann ich das verwirklichen?!?
Das Problem ist, dass das Programm mehrfach pro Sekunde gestartet wird und man dann immer den gleichen (wenn nicht sogar "selben") Vector erhält.

Danke und viele Grüße

SeppJ

railrun schrieb:

Wie kann ich das verwirklichen?!?

Was ist denn dein Problem dabei?

Das Problem ist, dass das Programm mehrfach pro Sekunde gestartet wird und man dann immer den gleichen (wenn nicht sogar "selben") Vector erhält.

Dann solltest du weitere Entropiequellen benutzen als nur die Uhrzeit. Etwas wo man noch leicht dran kommt und was innerhalb einer Sekunde ziemlich eindeutig ist, ist zum Beispiel die Prozessnummer. Viele Betriebssysteme bieten auch Quellen von echten oder auch Pseudozufallszahlen die du - je nach Anspruch - beim erzeugen des Seeds benutzen kannst.

(P.S.: Der Mersenne-Twister hat hier im Forum (durchaus zu Recht, wie ich finde) nicht ganz so den guten Ruf wie es die vor Lob überschäumende Wikipediaseite vermuten lässt. Es gibt genau so gute aber wesentlich schnellere PRNGs)

railrun

SeppJ schrieb:

(P.S.: Der Mersenne-Twister hat hier im Forum (durchaus zu Recht, wie ich finde) nicht ganz so den guten Ruf wie es die vor Lob überschäumende Wikipediaseite vermuten lässt. Es gibt genau so gute aber wesentlich schnellere PRNGs)

Danke SeppJ für die schnelle Antwort. Welchen RNG würdest du denn empfehlen?
Mein Problem ist, dass ich mít References&Pointern immer noch auf Kriegsfuss stehe und ich nicht weiß, wie "RandomNumberGenerator& rand" ich das einbinden soll... Ist vielleicht ein Armutszeugnis , aber bisher hab ich versucht mir alles selber beizubringen...

SeppJ

railrun schrieb:

SeppJ schrieb:

(P.S.: Der Mersenne-Twister hat hier im Forum (durchaus zu Recht, wie ich finde) nicht ganz so den guten Ruf wie es die vor Lob überschäumende Wikipediaseite vermuten lässt. Es gibt genau so gute aber wesentlich schnellere PRNGs)

Danke SeppJ für die schnelle Antwort. Welchen RNG würdest du denn empfehlen?

Kommt drauf an, wofür :p . Ein paar Strings zu shuffeln klingt eigentlich nach einem Fall für den Standardgenerator.

Mein Problem ist, dass ich mít References&Pointern immer noch auf Kriegsfuss stehe und ich nicht weiß, wie "RandomNumberGenerator& rand" ich das einbinden soll... Ist vielleicht ein Armutszeugnis , aber bisher hab ich versucht mir alles selber beizubringen...

Hmm, dann solltest du das vielleicht mal nachholen. Das (die Referenzen, nicht unbedingt die Pointer) sind ziemliche Grundlagen, um in C++ überhaupt irgendetwas machen zu können. Und ist auch nicht schwer, das kannst du in ein paar Stunden lernen und verstehen.

Die Referenz die du verlinkst zeigt ja schon ein Beispiel. Jedoch gehen die über drei Ecken, um alle Möglichkeiten zu zeigen. Vielleicht ist es dir so verständlicher:

int myrandom (int i) { return rand()%i;}

int main () {
  vector<int> myvector;
  for (int i=1; i<10; ++i) myvector.push_back(i); 

  random_shuffle ( myvector.begin(), myvector.end(), myrandom);
}

railrun

Hallo SeppJ,

ja, es steht ganz oben auf meine To-Learn-Liste

Aber die Standard-Funktion ist eben das Problem, da dass Programm mehrmals pro Sekunde aufgerufen wird. Hab es mir in einer Schleife ausgeben lassen und wer hätte es nicht gedacht

5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0 
5 4 8 9 1 6 3 2 7 0

314159265358979

Ich glaube eher du rufst srand() in deiner Schleife dauernd auf.

railrun

314159265358979 schrieb:

Ich glaube eher du rufst srand() in deiner Schleife dauernd auf.

Jein.
Ich rufe das Programm mehrfach pro Sekunde auf

314159265358979

Öhm ja, verlesen. Dann nimm doch einen anderen Seed, zum Beispiel die Nanosekunden.

railrun

314159265358979 schrieb:

Öhm ja, verlesen. Dann nimm doch einen anderen Seed, zum Beispiel die Nanosekunden.

Und wie bring ich es dem random_shuffle bei?!

314159265358979

Indem du einfach srand() aufrufst?

SeppJ

Ich wiederhole mich:

SeppJ schrieb:

railrun schrieb:

Das Problem ist, dass das Programm mehrfach pro Sekunde gestartet wird und man dann immer den gleichen (wenn nicht sogar "selben") Vector erhält.

Dann solltest du weitere Entropiequellen benutzen als nur die Uhrzeit. Etwas wo man noch leicht dran kommt und was innerhalb einer Sekunde ziemlich eindeutig ist, ist zum Beispiel die Prozessnummer. Viele Betriebssysteme bieten auch Quellen von echten oder auch Pseudozufallszahlen die du - je nach Anspruch - beim Erzeugen des Seeds benutzen kannst.

Da hilft dir auch der Mersenne Twister nichts, wenn du als Seed eine sekundengenaue Uhrzeit benutzt.

railrun

314159265358979 schrieb:

Indem du einfach srand() aufrufst?

So?!

int myrandom(int i) {
	return rand() % i;
}

int main() {
	srand(static_cast<int> (time(NULL)));
	vector<int> myvector;
	for (int i = 1; i < 10; ++i)
		myvector.push_back(i);

	random_shuffle(myvector.begin(), myvector.end(), myrandom);

	for (int j = 0; j < 10; j++) {
		cout << myvector[j] << " ";
	}
	cout << endl;
}

Da kommt das gleiche raus...

314159265358979

Liest du überhaupt, was SeppJ und ich schreiben?

SeppJ

314159265358979 schrieb:

Liest du überhaupt, was SeppJ und ich schreiben?

Auch wenn ich ebenfalls enttäuscht über das nicht vorhandene Mitdenken des Threaderstellers bin, hier trotzdem ein Beispiel, weil es prinzipiell über die Standard-Sprachmittel hinausgeht:

#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <iostream>

#ifdef _WIN32
 #include <windows.h>
#define GET_PID GetCurrentProcessId()
#elif defined(__linux) or defined (linux)
 #include <unistd.h>
 #define GET_PID getpid()
#else
 #error "Geht nur in Windows oder Linux"
#endif 

using namespace std;

int main() 
{
  srand(time(0)*GET_PID);
  vector<int> myvector;
  for (int i = 0; i < 10; ++i)
    myvector.push_back(i);

  random_shuffle(myvector.begin(), myvector.end());

  for (int j = 0; j < 10; j++) {
    cout << myvector[j] << " ";
  }
  cout << '\n';
}

Kann jemand den Windows-Pfad testen? Habe keines .

Das ist jetzt nur ein ganz rudimentäres Beispiel. Mit beispielsweise der boost Zufallszahlenbibliothek kann man sich das ganze systemabhängige Gefummel und das Nachschlagen aller Präprozessormakros sparen, weil das schon jemand erledigt hat. Oder alternativ bietet die Uhrzeitbibliothek von boost auch hochaufgelöste Timer, systemunabhängig gekapselt. Und es gibt die schon erwähnten Zufallszahlenquellen in verschiedenen Stärken, die von vielen Betriebssystemen angeboten werden.

edit: Und noch ein paar der schlimmeren Fehler und Ungenauigkeiten aus dem vom Threadersteller übernommenen Code entfernt.

railrun

314159265358979 schrieb:

Liest du überhaupt, was SeppJ und ich schreiben?

Den letzten Beitrag von SeppJ hab ich gerade erst gesehen, sorry.
Wenn du sagst, ich soll srand() aufrufen, dann sagt mir das herzlich wenig, sorry.
Ich hab jetzt mal geschaut, dass ich auf /dev/urandom bzw. /dev/random zugreife und dann srand((time(NULL)+seed)); aufrufe.

Aber danke für dir Hilfe... Das man immer gleich geflamed wird...

railrun

SeppJ schrieb:

edit: Und noch ein paar der schlimmeren Fehler und Ungenauigkeiten aus dem vom Threadersteller übernommenen Code entfernt.

Und welche wären das?

314159265358979

314159265358979 schrieb:

Öhm ja, verlesen. Dann nimm doch einen anderen Seed, zum Beispiel die Nanosekunden.

Und sag bloß nicht, du hast den Post auch überlesen. Du hast sogar darauf geantwortet.

SeppJ

railrun schrieb:

SeppJ schrieb:

edit: Und noch ein paar der schlimmeren Fehler und Ungenauigkeiten aus dem vom Threadersteller übernommenen Code entfernt.

Und welche wären das?

Zum Beispiel hast du nur 9 Elemente eingefügt, aber 10 ausgegeben.

Das myrandom war nicht ganz so sinnvoll. Klar das hast du von mir, aber das war eigentlich nur ein Beispiel, wie so eine Funktion aussehen kann. Aber rand selbst zu kapseln bringt herzlich wenig, da es schon der Standard ist.

Wenn du '\n' meinst, sag '\n', nicht endl, welches '\n' und flush entspricht.

Der staitc_cast war total unnötig.

Also (bis auf die Ausgabe über das Feldende hinaus) eher Kleinigkeiten. Der Unterschied zwischen 9 und 10 ist jedoch schon ein grober Fehler gewesen.

volkard

SeppJ schrieb:

srand(time(0)*GET_PID);

Sünde!
+ oder ^ waren doch voll in Ordnung (aber zu langweilig?).
Das Ergebnis der Plutimikation hat so viele Nullen am Ende wie beide Faktoren zusammen. Das heißt, mit * ballerst Du Dir die teuer besorgten Entropiebits einfach wieder raus.

314159265358979

volkard schrieb:

SeppJ schrieb:
srand(time(0)*GET_PID);
Sünde!
Das Ergebnis der Plutimikation hat so viele Nullen am Ende wie beide Faktoren zusammen.

railrun

314159265358979 schrieb:

314159265358979 schrieb:

Öhm ja, verlesen. Dann nimm doch einen anderen Seed, zum Beispiel die Nanosekunden.

Und sag bloß nicht, du hast den Post auch überlesen. Du hast sogar darauf geantwortet.

Da hätte ich auf eine etwas ausführlichere Erklärung gehofft...

Ich hab dich gefragt,

Und wie bring ich es dem random_shuffle bei?!

Deine Antwort darauf:

Indem du einfach srand() aufrufst?

Da ich damit nicht weiterkam, hab ich im Netz geschaut und es in meinem Code eingebaut...
Gegenfrage: Hast du es dir durchgelesen?!

@SeppJ
Zum Fehler... In der Tat... Die Schleife hab ich mir aus einem anderen Programm schnell rauskopiert, wo ich eine 2D-Vektor hatte. Danke für den Hinweis (das ist ehrlich gemeint!)
Static cast hatte ich aus einem Beispiel im Internet (siehe oben, meine Frage wie ich srand() aufrufen soll).