Verteilungen und interner Status

Question

Auf Stackoverflow gibt es viele Fragen zum Generieren von gleichmäßig verteilten Ganzzahlen aus unbekannten Prioritätsbereichen. Z.B.

• C++11 Generating random numbers from frequently changing range
• Vary range of uniform_int_distribution

Die typische Lösung ist so etwas wie:

inline std::mt19937 &engine() 
{ 
    thread_local std::mt19937 eng; 
    return eng; 
} 

int get_int_from_range(int from, int to) 
{ 
    std::uniform_int_distribution<int> dist(from, to); 
    return dist(engine()); 
} 

Da eine Verteilung ein leichtes Ziel sein sollte, und es gibt nicht die Leistung betrifft Neuer es mehr Mal scheint es, dass selbst einfache Verteilung sehr gut und in der Regel some internal state haben wird.

So habe ich mich gefragt, ob die Verteilung durch ständiges Zurücksetzen stören (d. H. Wiederherstellung der Verteilung bei jedem Aufruf von get_int_from_range) Ich bekomme richtig verteilt Ergebnisse.

Es gibt eine long discussion zwischen Pete Becker und Steve Jessop, aber ohne ein abschließendes Wort. In einer anderen Frage (Should I keep the random distribution object instance or can I always recreate it?) scheint das "Problem" des internen Zustands nicht sehr wichtig.

Gibt der C++ - Standard eine Garantie für dieses Thema?

Ist die folgende Implementierung (von N4316 - std::rand replacement) etwas zuverlässiger?

int get_int_from_range(int from, int to) 
{ 
    using distribution_type = std::uniform_int_distribution<int>; 
    using param_type = typename distribution_type::param_type; 

    thread_local std::uniform_int_distribution<int> dist; 
    return dist(engine(), param_type(from, to));  
} 

EDIT

Diese wieder verwendet einen möglichen internen Zustand einer Verteilung, aber es ist komplex, und ich bin nicht sicher, ob es die Mühe wert macht:

int get_int_from_range(int from, int to) 
{ 
    using range_t = std::pair<int, int>; 
    using map_t = std::map<range_t, std::uniform_int_distribution<int>>; 

    thread_local map_t range_map; 

    auto i = range_map.find(range_t(from, to)); 
    if (i == std::end(range_map)) 
    i = range_map.emplace(
      std::make_pair(from, to), 
      std::uniform_int_distribution<int>{from, to}).first; 

    return i->second(engine()); 
} 

^{(von https://stackoverflow.com/a/30097323/3235496)}

Answer 1

Interessante Frage.

Also habe ich mich gefragt, ob mit stören, wie die Verteilung Arbeiten von es ständig zurückzusetzen (das heißt die Verteilung bei jedem Aufruf von get_int_from_range Neuer) ich richtig Ergebnisse verteilt bekommen.

Ich habe Code geschrieben, um dies mit uniform_int_distribution und poisson_distribution zu testen. Es ist einfach genug, dies zu erweitern, um eine andere Distribution zu testen, wenn Sie es wünschen. Die Antwort scheint zu sein ja.

Boiler-Plate-Code:

#include <random> 
#include <memory> 
#include <chrono> 
#include <utility> 

typedef std::mt19937_64 engine_type; 

inline size_t get_seed() 
    { return std::chrono::system_clock::now().time_since_epoch().count(); } 

engine_type& engine_singleton() 
{ 
    static std::unique_ptr<engine_type> ptr; 

    if (!ptr) 
     ptr.reset(new engine_type(get_seed())); 
    return *ptr; 
} 

// ------------------------------------------------------------------------ 

#include <cmath> 
#include <cstdio> 
#include <vector> 
#include <string> 
#include <algorithm> 

void plot_distribution(const std::vector<double>& D, size_t mass = 200) 
{ 
    const size_t n = D.size(); 
    for (size_t i = 0; i < n; ++i) 
    { 
     printf("%02ld: %s\n", i, 
      std::string(static_cast<size_t>(D[i]*mass),'*').c_str()); 
    } 
} 

double maximum_difference(const std::vector<double>& x, const std::vector<double>& y) 
{ 
    const size_t n = x.size(); 

    double m = 0.0; 
    for (size_t i = 0; i < n; ++i) 
     m = std::max(m, std::abs(x[i]-y[i])); 

    return m; 
} 

-Code für die eigentlichen Tests:

#include <iostream> 
#include <vector> 
#include <cstdio> 
#include <random> 
#include <string> 
#include <cmath> 

void compare_uniform_distributions(int lo, int hi) 
{ 
    const size_t sample_size = 1e5; 

    // Initialize histograms 
    std::vector<double> H1(hi-lo+1, 0.0), H2(hi-lo+1, 0.0); 

    // Initialize distribution 
    auto U = std::uniform_int_distribution<int>(lo,hi); 

    // Count! 
    for (size_t i = 0; i < sample_size; ++i) 
    { 
     engine_type E(get_seed()); 

     H1[ U(engine_singleton())-lo ] += 1.0; 
     H2[ U(E)-lo ] += 1.0; 
    } 

    // Normalize histograms to obtain "densities" 
    for (size_t i = 0; i < H1.size(); ++i) 
    { 
     H1[i] /= sample_size; 
     H2[i] /= sample_size; 
    } 

    printf("Engine singleton:\n"); plot_distribution(H1); 
    printf("Engine creation :\n"); plot_distribution(H2); 
    printf("Maximum difference: %.3f\n", maximum_difference(H1,H2)); 
    std::cout<< std::string(50,'-') << std::endl << std::endl; 
} 

void compare_poisson_distributions(double mean) 
{ 
    const size_t sample_size = 1e5; 
    const size_t nbins = static_cast<size_t>(std::ceil(2*mean)); 

    // Initialize histograms 
    std::vector<double> H1(nbins, 0.0), H2(nbins, 0.0); 

    // Initialize distribution 
    auto U = std::poisson_distribution<int>(mean); 

    // Count! 
    for (size_t i = 0; i < sample_size; ++i) 
    { 
     engine_type E(get_seed()); 
     int u1 = U(engine_singleton()); 
     int u2 = U(E); 

     if (u1 < nbins) H1[u1] += 1.0; 
     if (u2 < nbins) H2[u2] += 1.0; 
    } 

    // Normalize histograms to obtain "densities" 
    for (size_t i = 0; i < H1.size(); ++i) 
    { 
     H1[i] /= sample_size; 
     H2[i] /= sample_size; 
    } 

    printf("Engine singleton:\n"); plot_distribution(H1); 
    printf("Engine creation :\n"); plot_distribution(H2); 
    printf("Maximum difference: %.3f\n", maximum_difference(H1,H2)); 
    std::cout<< std::string(50,'-') << std::endl << std::endl; 

} 

// ------------------------------------------------------------------------ 

int main() 
{ 
    compare_uniform_distributions(0, 25); 
    compare_poisson_distributions(12); 
} 

Run es here.

---

der Standard C++ Hat zu diesem Thema keine Garantie machen?

Nicht, dass ich weiß. Ich würde jedoch sagen, dass der Standard eine implizite Empfehlung abgibt, die Engine nicht jedes Mal neu zu erstellen. für jede Verteilung Distrib, der Prototyp Distrib::operator() nimmt eine Referenz URNG& und nicht eine const Referenz. Dies ist erforderlich, verständlicherweise, weil der Motor brauchen könnte seinen internen Zustand zu aktualisieren, aber es bedeutet auch, dass Code suchen, wie dieses

auto U = std::uniform_int_distribution(0,10); 
for (<something here>) U(engine_type()); 

lässt sich nicht kompilieren, die mir ein klarer Anreiz ist nicht Code wie diesen zu schreiben.

---

Ich bin sicher, es gibt viele Ratschläge da draußen, wie man die zufällige Bibliothek richtig verwendet. Es ist kompliziert, wenn Sie die Möglichkeit der Verwendung von random_device s und ermöglicht determinis Seeding für Testzwecke zu handhaben, aber ich dachte, es nützlich sein könnte, meine eigene Empfehlung da draußen zu werfen:

es

#include <random> 
#include <chrono> 
#include <utility> 
#include <functional> 

inline size_t get_seed() 
    { return std::chrono::system_clock::now().time_since_epoch().count(); } 

template <class Distrib> 
using generator_type = std::function< typename Distrib::result_type() >; 

template <class Distrib, class Engine = std::mt19937_64, class... Args> 
inline generator_type<Distrib> get_generator(Args&&... args) 
{ 
    return std::bind(Distrib(std::forward<Args>(args)...), Engine(get_seed())); 
} 

// ------------------------------------------------------------------------ 

#include <iostream> 

int main() 
{ 
    auto U = get_generator<std::uniform_int_distribution<int>>(0,10); 
    std::cout<< U() << std::endl; 
} 

Run here. Hoffe das hilft!

BEARBEITEN Meine erste Empfehlung war ein Fehler, und ich entschuldige mich dafür; Wir können keine Singleton-Engine wie in den obigen Tests verwenden, weil dies bedeuten würde, dass zwei uniforme int-Verteilungen die gleiche zufällige Sequenz erzeugen würden. Stattdessen verlasse ich mich auf die Tatsache, dass std::bind die neu erstellte Engine lokal in std::function mit einem eigenen Seed kopiert, und dies ergibt das erwartete Verhalten; verschiedene Generatoren mit der gleichen Verteilung erzeugen unterschiedliche zufällige Sequenzen.