Schneller Zufallsgenerator für Monte Carlo
-
Hm, nagut, da kommt halt noch dazu, dass ich vermute, dass der Zufallsgenerator tatsächlich nicht der Flaschenhals ist. Denn die iterative Variante ist in etwa genau so schnell. Ich bin auch einfach nicht sehr in der Zufallstheorie drin. Die Zufallszahlen sollen möglichst zufällig sein, umfassen jedoch einen Zahlenraum von <1 Mio. Einträgen.
-
Eisflamme schrieb:
Hm, nagut, da kommt halt noch dazu, dass ich vermute, dass der Zufallsgenerator tatsächlich nicht der Flaschenhals ist.
Das heißt, du hast optimiert, ohne vorher zu messen. Das macht man einfach nicht.
Denn die iterative Variante ist in etwa genau so schnell. Ich bin auch einfach nicht sehr in der Zufallstheorie drin. Die Zufallszahlen sollen möglichst zufällig sein, umfassen jedoch einen Zahlenraum von <1 Mio. Einträgen.
Ein Münzwurf hat auch nur zwei Werte, ist aber eine Quelle für hochwertige Zufallszahlen. Der Zahlenbereich sagt überhaupt nichts aus.
-
SeppJ schrieb:
Eisflamme schrieb:
Den Rest habe ich gar nicht erst getestet.
Solltest du aber. Der MT ist ehrlich gesagt nicht soooo schnell, selbst verglichen mit anderen "guten" Zufallsgeneratoren. Erst recht, wenn du ihn mit einem ultra-einfachen Generator vergleichst.
Link bitte, sonst glaub ich das mal einfach nicht.
ps: Ich begründe meine Aussage hierauf: http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/performance.html
-
SeppJ:
Den Algorithmus hatte ich schon vorher optimiert, weil ich ihn erst ohne Monte Carlo liefen ließ, da ich dachte, dass das reicht. Es zeigt sich jedoch, dass es Szenarien gibt, in denen die Laufzeit zu lang wäre, da liefert aber Monte Carlo super Annäherungen.Dass der Zahlenbereich nichts sagt, ist ja ok... ich dachte, vielleicht hilft dieses Detail irgendwie.
-
Wichtig ist die Periodenlänge die du brauchst, und in wie vielen Dimensionen die Zahlen gleichverteilt sein müssen.
MT ist bei beiden Kriterien ziemlich gut.
Und sollte IMO ausreichend schnell sein.
-
hustbaer schrieb:
ps: Ich begründe meine Aussage hierauf: http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/performance.html
Komisch, ich auch.
Alternativ auch hier:
http://www.gnu.org/software/gsl/manual/html_node/Random-Number-Generator-Performance.htmlWas spricht denn beispielsweise gegen TAUS? Ist auch ein sehr guter Generator.
-
SeppJ schrieb:
hustbaer schrieb:
ps: Ich begründe meine Aussage hierauf: http://www.boost.org/doc/libs/1_51_0/doc/html/boost_random/performance.html
Komisch, ich auch.
naja, wir reden hier von <10% performance unterschied zum absolut schnellsten gemessen Generator. Im Vergleich zu der Bandbreite die die Generatoren da haben ist es für mich reichlich übertrieben zu bhaupten, dass der MT nicht "sooo schnell" ist. Im Gegenteil. dafür dass er eine viel viel längere Zykluslänge erreicht und in hochdimensionalen räumen noch gute Resutlate erzielt, sind 7% gar nichts.
-
Eine dumme Frage. Welche Anforderungen stellen sich neben der Geschwindigkeit an den Zufallsgenerator?
Wäre es auch denkbar den RC4 Algorithmus als eine Zufallszahlengenerator zu missbrauchen?
-
Bitte ein Bit schrieb:
Eine dumme Frage. Welche Anforderungen stellen sich neben der Geschwindigkeit an den Zufallsgenerator?
Das kommt eben drauf an
. Bei den meisten MC-Simulationen sind die Anforderungen sehr gering:
- Die Verteilung der Zufallszahlen sollte stimmen. In den meisten Fällen will man also, dass der Generator statistischen Tests auf Gleichverteilung genügt, daraus kann man sich dann beliebige andere Verteilungen berechnen.
- Die Periodenlänge (falls der Generator eine Periode hat) sollte in der gleichen Größenordnung oder größer als die Zahl der (insgesamt) benutzten Zufallszahlen sein. Auf keinen Fall will man eine Periodenlänge in der Größenordnung eines "Schritts" (was auch immer dies genau für die konkrete Simulation heißt) oder gar kürzer. Dies schließt für viele Simulationen die gaaaaanz einfachen Generatoren aus den 60er Jahren aus.
- Die Zahlen sollten möglichst "zufällig" sein. Die Definition davon ist ein bisschen heikel. Sagen wir: Die Zahlen sollten möglichst viele statistischen Tests auf genügen, denen auch echte Zufallszahlen genügen. Dazu testet man in der Regel Korrelationen zwischen Zahlen und Zahlenpaaren.Insgesamt kommt man bei MC mit erstaunlich viel Schluderei davon. Wichtig ist, dass man richtig sampled und überhaupt das Modell stimmt. Selbst da kann man ein bisschen pfuschen, wenn man weiß, was man tut. Einen LCG würde ich aber dennoch nicht nehmen. Da ist unmittelbar ersichtlich, dass die Hyperflächenverteilung zu Problemen führen könnte und es ist nicht so, als gäbe es keine Alternativen.
Wäre es auch denkbar den RC4 Algorithmus als eine Zufallszahlengenerator zu missbrauchen?
Klar, warum nicht? Ist aber totaler Overkill.
-
Also da ich mit diesem Algorithmus nur Zahlen aus Arrays picken möchte, generiere ich lediglich einen zufälligen Index. Dieser liegt im Bereich von 0 bis (52 über 5). Hilft das irgendwie?
-
Eisflamme schrieb:
Hallo,
es handelt sich um ein Poker-Analyseprogramm, bei dem die Boards ausgewertet werden sollen. "Boards" sind dabei die 5 Karten in der Mitte. Somit handelt es sich um 52 über 5 Möglichkeiten. Diese Möglichkeiten sollen über den Zufallsgenerator ermittelt werden, denn Ziel ist es zu berechnen, wie häufig mehrere Spieler mit unterschiedlichen Händen gewinnen. Dabei kann Spieler 1 z.B. 100 unterschiedliche Handkombinationen halten, Spieler 2 100 andere. Dann haben wir schon 100 * 100 * (48 über 2) Berechnungen. Und das Szenario mit nur zwei Spielern und nur 100 Kombinationen pro Spieler ist optimistisch.
Was willst du berechnen? Die Wahrscheinlichkeit, dass einer gewinnt, obwohl du nicht weißt, was für Karten alle haben?
Geht doch garnicht.
-
Geht wohl, wenn man deren Hände eingrenzen kann. Man muss nicht die genaue Hand kennen, es reicht auch eine Range von möglichen Händen. Auch wenn ein Spieler eine zufällige Hand hält, lässt sich die Wahrscheinlichkeit berechnen. Halten beide zufällige Hände, ist Gewinn + Split/2 natürlich 50%.
