Inhaltsverzeichnis
<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 rand() aus <cstdlib> hinausgehen.
#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() << ' '; } }
Anmerkung: std::random_device
ist bei älteren MinGW-Compilern unter Windows noch nicht zufällig;
der Fehler wurde in g++ 9.2 behoben.1)
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.
std::mt19937 engine1, engine2; std::stringstream state; state << engine1; state >> engine2; assert(engine1 == engine2);
Vorgefertigte (pseudozufällige) Generator-Engines (Tabelle) sind Spezialisierungen von Schablonen, die bekannten Algorithmen folgen:
- Ein 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 Fibonacci-Generator).
- Mersenne-Twister bieten sehr lange Perioden ohne Wiederholungen.
- Eine
discard_block_engine<Engine, p, r>
überspringt nachr
Werten die restlichen Werte einer von der Basis-Engine erzeugten Folge ausn
Werten. - Eine
independent_bits_engine<Engine, w, Zieltyp>
kombiniertw
Bits der Basis-Engine zum Zieltyp. - Die
shuffle_order_engine<Engine, k>
liefert jeweilsk
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_base | subtraktiver Generator mit Übertrag, 48bit |
ranlux24 | nimmt 23 von 223 erzeugten Werten |
ranlux48 | nimmt 11 von 389 erzeugten Werten |
knuth_b | Shuffle-Algorithmus von Donald E. Knuth |
default_random_engine | 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 Ausgabe-Iterator out
.
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 << ' ';
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 |
---|---|---|
Diskrete Gleichverteilunguniform_int_distribution (a = 0, b = numeric_limits<int>::max) | $P(i|a,b) = \frac{1}{b-a+1}$ | $a \leq i \leq b$ |
Stetige Gleichverteilunguniform_real_distribution (a = 0.0, b = 1.0) | $p(x|a,b) = \frac{1}{b-a}$ | $a\leq x<b$ |
Bernoulli-Verteilungbernoulli_distribution (p = 0.5) | $P(b|p) = \left\lbrace \begin{array}{l}p \\ 1-p\end{array} \right.$ | true ,false |
Binomialverteilungbinomial_distribution (n = 1, p = 0.5) | $P(i|n,p) = {n \choose i} p^i (1-p)^{n-i}$ | $0\leq i\leq n$ |
Geometrische Verteilunggeometric_distribution (p = 0.5) | $P(i|p) = p (1-p)^i$ | $0\leq i$ |
Negative Binomialverteilungnegative_binomial_distribution (n = 1, p = 0.5) | $P(i|n,p) = {n+i+1 \choose i} p^n (1-p)^i$ | $0\leq i$ |
Poisson-Verteilungpoisson_distribution (mu = 1.0) | $P(i|\mu) = \frac{e ^ \mu \mu ^i}{i!}$ | $0\leq i$ |
Exponentialverteilungexponential_distribution (lambda = 1.0) | $p(x|\lambda) = \lambda e ^{-\lambda x}$ | $0<x$ |
Gammaverteilunggamma_distribution (alpha = 1.0, beta = 1.0) | $p(x|\alpha, \beta) = \frac{e ^ {\alpha/\beta}}{\beta ^\alpha \Gamma(\alpha)}x ^{\alpha-1}$ | $0<x$ |
Weibull-Verteilungweibull_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$ |
Gumbel-Verteilungextreme_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} $ |
Normalverteilungnormal_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} $ |
Logarithmische Normalverteilunglognormal_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$ |
Chi-Quadrat-Verteilungchisquared_distribution (n = 1) | $p(x|n) = \frac{x^{n/2 - 1} e ^{-x/2}}{\Gamma(n/2) 2^{n/2}}$ | $0<x$ |
Cauchy-Verteilungcauchy_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}$ |
F-Verteilungfisher_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$ |
Studentsche t-Verteilungstudent_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}$ |
Dreiecksverteilungpiecewise_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}$ |