namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


kennen:include:random

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

kennen:include:random [2015-02-15 14:09] (aktuell)
Zeile 1: Zeile 1:
 +====== <​random>​ ======
 +===== Einsatzbeispiel =====
 +C++ stellt miteinander kombinierbare Klassen zur Erzeugung (pseudo)zufälliger Zahlen ([[#​Generatoren]]),​ [[#​Saatwerte]] und [[#​Verteilungen]] bereit,
 +deren Möglichkeiten weit über die der C-Funktion [[..:​lib:​rand|rand()]] aus [[.:​cstdlib]] hinausgehen.
 +
 +<code cpp>
 +#include <​ctime>​
 +#include <​functional>​
 +#include <​iostream>​
 +#include <​random>​
 +
 +void zufall()
 +{
 +#if defined(__MINGW32__) || defined(__MINGW64__)
 +  std::​mt19937 engine(std::​time(nullptr));​ // siehe Anmerkung unten
 +#​else  ​
 +  std::​random_device rd;
 +  std::​mt19937 engine(rd());​
 +#​endif  ​
 +  std::​normal_distribution<>​ normal;
 +  std::​function<​double()>​ random = std::​bind(normal,​ engine);
 +  ​
 +  for (int i = 0; i < 20; ++i)
 +  {
 +    std::cout << random() << ' ';
 +  }
 +}
 +</​code>​
 +Anmerkung: ''​std::​random_device''​ ist beim MinGW-Compiler g++ 4.9.2 unter Windows (noch) nicht zufällig.
 +Die Initialisierung mit der Systemzeit ''​std::​time(nullptr)''​ oder "​moderner",​ aber barocker mit
 +''​std::​chrono::​system_clock::​now().time_since_epoch().count()''​ ist ein Hack für unkritische Anwendungen.
 +Für kryptographisch sichere Saatwerte müsste auf Mittel des Betriebssystems zurückgegriffen werden. ​
 +===== Generatoren =====
 +Zufallsgeneratoren sind Funktionsobjekte,​ die beim Aufruf ''​g()'' ​
 +einen Ganzzahlwert aus dem geschlossenen Intervall ''​[g.min(),​ g.max()]''​ liefern.
 +Ein Funktionsobjekt ''​g''​ heißt //Engine//,
 +wenn es im Konstruktor eine Saatfolge übernehmen kann, 
 +die auch über ''​g.seed(seq)''​ wiederherstellbar ist.
 +Mit ''​g.discard(n)''​ wird eine Anzahl von Zufallswerten übersprungen.
 +Der Zustand einer Engine lässt sich in einen Strom schreiben bzw. 
 +aus einem Strom wiederherstellen.
 +Mit Vergleichsoperatoren kann die Gleichheit der Zustände geprüft werden.
 +
 +<code cpp>
 +std::​mt19937 engine1, engine2;
 +std::​stringstream state;
 +state << engine1;
 +state >> engine2;
 +assert(engine1 == engine2);
 +</​code>​
 +
 +Vorgefertigte Generator-Engines (Tabelle) sind Spezialisierungen von Schablonen:
 +  * Ein [[wpde>​linearer Kongruenzgenerator]] (LCG) erzeugt Wertfolgen $ x_{n+1}=(a x_n + c) \mod m $,
 +  * ein subtraktiver Generator mit einer Vorschrift $ x_{n+1}=(x_{n-s} - x_{n-r} - c) \mod m $ (verallgemeinerter verzögerter [[wpde>​Kongruenzgenerator#​Fibonacci-Generator|Fibonacci-Generator]]).
 +  * [[wpde>​Mersenne-Twister]] bieten sehr lange Perioden ohne Wiederholungen.
 +  * Eine ''​discard_block_engine<​Engine,​ p, r>''​ überspringt nach ''​r''​ Werten die restlichen Werte einer von der Basis-Engine erzeugten Folge  aus ''​n''​ Werten.
 +  * Eine ''​independent_bits_engine<​Engine,​ w, Zieltyp>''​ kombiniert ''​w''​ Bits der Basis-Engine zum Zieltyp.
 +  * Die ''​shuffle_order_engine<​Engine,​ k>''​ liefert jeweils ''​k''​ Werte der Basis-Engine in veränderter Reihenfolge.
 +
 +==== Generatortypen ====
 +Die Qualität eines Generators hängt stark von den gewählten Konstanten ab.
 +Im Namensraum ''​std''​ sind folgende Generatoren (Engines) definiert:
 +|''​minstd_rand0'' ​ |LCG mit $a=16807$, $c=0$, $m=2^{31}-1$ |
 +|''​minstd_rand'' ​  |LCG mit $a=48271$, $c=0$, $m=2^{31}-1$ |
 +|''​mt19937'' ​      ​|Mersenne-Twister 32bit |
 +|''​mt19937_64'' ​   |Mersenne-Twister 64bit |
 +|''​ranlux24_base''​ |subtraktiver Generator mit Übertrag, 24bit |
 +|''​ranlux48'' ​     |nimmt 23 von 223 erzeugten Werten |
 +|''​ranlux48'' ​     |nimmt 11 von 389 erzeugten Werten |
 +|''​knuth_b'' ​      ​|Shuffle-Algorithmus von Donald E. Knuth |
 +|''​default_random_engine''​ |einfacher, implementierungsabhängiger Generator |
 +
 +===== Saatwerte =====
 +Saatwert-Folgen ''​std::​seed_seq s(first,​last)''​ initialisieren Engines,
 +''​s.generate(first,​last)''​ befüllt den angebenen Bereich ''​[first,​last)'',​
 +''​s.param(out)''​ schreibt ''​s.size()''​ Werte in den [[..:​stl#​Iteratoren|Ausgabe-Iterator]] ''​out''​.
 +
 +<code cpp>
 +std::​seed_seq seed = {std::​time(nullptr)};​
 +std::​vector<​unsigned int> v(10);
 +seed.generate(begin(v),​ end(v));
 +for (auto e : v) std::cout << e << ' ';
 +</​code>​
 +===== Verteilungen =====
 +Verteilungen ''​D(''//​parameter//''​)''​ erzeugen mit dem Ganzzahl-Generator ''​g''​ beim Aufruf ''​d(g)''​
 +bzw. ''​d(g,​ d.param())''​ eine Zufallszahl nach dem zugehörigen Verteilungsgesetz im Intervall ''​[d.min(),​ d.max()]''​.
 +Die Parameter ''​p''​ der Verteilung lassen sich auslesen und mit ''​d.param(p)''​ setzen
 +sowie mit I/​O-Operatoren in Ströme schreiben bzw. daraus lesen. ​
 +Nach ''​d.reset()''​ hängen nachfolgende Werte nicht mehr von bisher erzeugten ab.
 +
 +==== Verteilungsgesetze ====
 +im Namensraum ''​std''​ definierte Klassen:
 +^Verteilung\\ (Konstruktorparameter,​ Vorgabewerte)^Verteilungsfunktion / Dichtefunktion ^Wertebereich^
 +|[[wpde>​Diskrete Gleichverteilung]]\\ ''​uniform_int_distribution''​\\ ''​(a = 0, b = numeric_limits<​int>::​max)''​|$P(i|a,​b) = \frac{1}{b-a+1}$|$a \leq i \leq b$|
 +|[[wpde>​Stetige Gleichverteilung]]\\ ''​uniform_real_distribution''​\\ ''​(a = 0.0, b = 1.0)''​|$p(x|a,​b) = \frac{1}{b-a}$|$a\leq x<b$|
 +|[[wpde>​Bernoulli-Verteilung]]\\ ''​bernoulli_distribution''​\\ ''​(p = 0.5)''​|$P(b|p) = \left\lbrace \begin{array}{l}p \\ 1-p\end{array} \right.$|''​true'',​\\ ''​false''​|
 +|[[wpde>​Binomialverteilung]]\\ ''​binomial_distribution''​\\ ''​(n = 1, p = 0.5)''​|$P(i|n,​p) = {n \choose i} p^i (1-p)^{n-i}$|$0\leq i\leq n$|
 +|[[wpde>​Geometrische Verteilung]]\\ ''​geometric_distribution''​\\ ''​(p = 0.5)''​|$P(i|p) = p (1-p)^i$|$0\leq i$|
 +|[[wpde>​Negative Binomialverteilung]]\\ ''​negative_binomial_distribution''​\\ ''​(n = 1, p = 0.5)''​|$P(i|n,​p) = {n+i+1 \choose i} p^n (1-p)^i$|$0\leq i$|
 +|[[wpde>​Poisson-Verteilung]]\\ ''​poisson_distribution''​\\ ''​(mu = 1.0)''​|$P(i|\mu) = \frac{e ^ \mu \mu ^i}{i!}$|$0\leq i$|
 +|[[wpde>​Exponentialverteilung]]\\ ''​exponential_distribution''​\\ ''​(lambda = 1.0)''​|$p(x|\lambda) = \lambda e ^{-\lambda x}$|$0<​x$|
 +|[[wpde>​Gammaverteilung]]\\ ''​gamma_distribution''​\\ ''​(alpha = 1.0, beta = 1.0)''​|$p(x|\alpha,​ \beta) = \frac{e ^ {\alpha/​\beta}}{\beta ^\alpha \Gamma(\alpha)}x ^{\alpha-1}$|$0<​x$|
 +|[[wpde>​Weibull-Verteilung]]\\ ''​weibull_distribution''​\\ ''​(a = 1.0, b = 1.0)''​|$p(x|a,​ b) = \frac{a}{b} \left(\frac{x}{b}\right)^{a-1} e ^{-(x/​b)^a}$|$0\leq x$|
 +|[[wpde>​Gumbel-Verteilung]]\\ ''​extreme_value_distribution''​\\ ''​(a = 0.0, b = 1.0)''​|$p(x|a,​ b) = \frac{1}{b} e ^{-\gamma - e^{-\gamma}}$,​ $\gamma = {x-a}/b$|$x \in \mathbb{R} $|
 +|[[wpde>​Normalverteilung]]\\ ''​normal_distribution''​\\ ''​(mu = 0.0, sigma = 1.0)''​|$p(x|\mu,​ \sigma) = \frac{1}{\sigma \sqrt{2 \pi}} e ^{-\frac{(x-\mu)^2}{2 \sigma^2}}$|$x \in \mathbb{R} $|
 +|[[wpde>​Logarithmische Normalverteilung]]\\ ''​lognormal_distribution''​\\ ''​(mu = 0.0, sigma = 1.0)''​|$p(x|\mu,​ \sigma) = \frac{1}{x \sigma \sqrt{2 \pi}} e ^{-\frac{(\ln x-\mu)^2}{2 \sigma^2}}$|$0<​x$|
 +|[[wpde>​Chi-Quadrat-Verteilung]]\\ ''​chisquared_distribution''​\\ ''​(n = 1)''​|$p(x|n) = \frac{x^{n/​2 - 1} e ^{-x/​2}}{\Gamma(n/​2) 2^{n/​2}}$|$0<​x$|
 +|[[wpde>​Cauchy-Verteilung]]\\ ''​cauchy_distribution''​\\ ''​(a = 0.0, b = 1.0)''​|$p(x|a,​ b) = \frac{1}{\pi}\frac{b}{(x-a)^2+b^2}$|$x \in \mathbb{R}$|
 +|[[wpde>​F-Verteilung]]\\ ''​fisher_f_distribution''​\\ ''​(m = 1, n = 1)''​|$p(x|m,​ n) = \frac{\Gamma({m+n}/​2)}{\Gamma(m/​2)\Gamma(n/​2)}\left(\frac{m}{n}\right)^{m/​2} x^{m/​2-1}(1+\frac{mx}{n})^{-{m+n}/​2}$|$0\leq x$|
 +|[[wpde>​Studentsche t-Verteilung]]\\ ''​student_t_distribution''​\\ ''​(n = 1)''​|$p(x|n) = \frac{1}{\sqrt{n \pi}} \frac{\Gamma({n-1}/​2)}{\Gamma(n/​2)} \left(1 +\frac{x^2}{2}\right)^{-{n+1}/​2}$|$x \in \mathbb{R}$|
 +|''​discrete_distribution''​\\ ''​(firstW,​ lastW)''​|$P(i|p_0,​...,​p_{n-1}) = p_i$ mit $p_i = \frac{w_i}{S}$,​ $S=\sum_{k=0}^{n-1}{w_i}$,​ $w_i > 0$|$0\leq i<n$|
 +|''​piecewise_constant_distribution''​\\ ''​(firstb,​ lastb, firstW)''​|$p(x|p_0,​...,​p_{n-1},​\rho_0,​...,​\rho_{n-1}) = \frac{\rho_i}{b_{i+1}-b_i}$\\ mit $\rho_i = \frac{w_i}{S}$,​ $S= \sum_{k=0}^{n-1}{w_k}$|$b_i\leq x<​b_{i+1}$|
 +|[[wpde>​Dreiecksverteilung]]\\ ''​piecewise_linear_distribution''​\\ ''​(firstb,​ lastb, firstW)''​|$p(x|p_0,​...,​p_{n-1},​\rho_0,​...,​\rho_{n-1}) = \frac{b_{i+1}-x}{b_{i+1}-b_i}\rho_i+ \frac{x-b_i}{b_{i+1}-b_i}\rho_{i+1}$\\ mit $\rho_i = \frac{w_i}{S}$,​ $S = \frac{1}{2} \sum_{k=0}^{n-1}{(w_k+w_{k+1}) (b_{k+1}-b_k)}$|$b_i\leq x<​b_{i+1}$|
 +
 +
  
kennen/include/random.txt · Zuletzt geändert: 2015-02-15 14:09 (Externe Bearbeitung)