| |
— | kennen:include:random [2021-02-07 14:58] (aktuell) – angelegt - Externe Bearbeitung 127.0.0.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 bei älteren MinGW-Compilern unter Windows noch nicht zufällig; |
| der Fehler wurde in g++ 9.2 behoben.(( |
| https://stackoverflow.com/questions/18880654/why-do-i-get-the-same-sequence-for-every-run-with-stdrandom-device-with-mingw |
| )) |
| |
| 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 (pseudozufällige) Generator-Engines (Tabelle) sind Spezialisierungen von Schablonen, die bekannten Algorithmen folgen: |
| * 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_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 [[..: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}$| |
| |
| |
| |