namespace cpp

C++ lernen, kennen, anwenden

Benutzer-Werkzeuge

Webseiten-Werkzeuge


kennen:include:random

<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 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.

std::mt19937 engine1, engine2;
std::stringstream state;
state << engine1;
state >> engine2;
assert(engine1 == engine2);

Vorgefertigte Generator-Engines (Tabelle) sind Spezialisierungen von Schablonen:

  • 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 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 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 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$
Stetige Gleichverteilung
uniform_real_distribution
(a = 0.0, b = 1.0)
$p(x|a,b) = \frac{1}{b-a}$$a\leq x<b$
Bernoulli-Verteilung
bernoulli_distribution
(p = 0.5)
$P(b|p) = \left\lbrace \begin{array}{l}p \\ 1-p\end{array} \right.$true,
false
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$
Geometrische Verteilung
geometric_distribution
(p = 0.5)
$P(i|p) = p (1-p)^i$$0\leq i$
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$
Poisson-Verteilung
poisson_distribution
(mu = 1.0)
$P(i|\mu) = \frac{e ^ \mu \mu ^i}{i!}$$0\leq i$
Exponentialverteilung
exponential_distribution
(lambda = 1.0)
$p(x|\lambda) = \lambda e ^{-\lambda x}$$0<x$
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$
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$
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} $
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} $
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$
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$
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}$
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$
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,\ldots,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,\ldots,p_{n-1},\rho_0,\ldots,\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}$
Dreiecksverteilung
piecewise_linear_distribution
(firstb, lastb, firstW)
$p(x|p_0,\ldots,p_{n-1},\rho_0,\ldots,\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)