uniform_int_distribution - random ints c++
Distribuciones y estado interno. (1)
En Stackoverflow hay muchas preguntas sobre la generación de enteros distribuidos uniformemente a partir de rangos desconocidos de un priorato. P.ej
- C ++ 11 Generando números aleatorios de rango cambiando frecuentemente
- Variar la gama de uniform_int_distribution
La solución típica es algo como:
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());
}
Dado que una distribución debe ser un objeto liviano y no hay problemas de rendimiento que lo recrean varias veces, parece que incluso una distribución simple puede muy bien y generalmente tendrá algún estado interno .
Así que me preguntaba si interferir con el funcionamiento de la distribución al restablecerla constantemente (es decir, get_int_from_range la distribución en cada llamada de get_int_from_range ) obtengo resultados distribuidos correctamente.
Hay una larga discusión entre Pete Becker y Steve Jessop, pero sin una palabra final. En otra pregunta ( ¿Debo mantener la instancia de objeto de distribución aleatoria o siempre puedo volver a crearla? ) El "problema" del estado interno no parece ser muy importante.
¿El estándar C ++ ofrece alguna garantía con respecto a este tema?
¿Es la siguiente implementación (de N4316 - std :: rand replacement ) algo más confiable?
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));
}
EDITAR
Esto reutiliza un posible estado interno de una distribución, pero es complejo y no estoy seguro de que valga la pena:
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());
}
(de https://stackoverflow.com/a/30097323/3235496 )
Interesante pregunta.
Así que me preguntaba si interferir con el funcionamiento de la distribución al restablecerla constantemente (es decir, volver a crear la distribución en cada llamada de get_int_from_range) obtengo resultados distribuidos correctamente.
He escrito código para probar esto con uniform_int_distribution y poisson_distribution . Es bastante fácil extender esto para probar otra distribución si lo desea. La respuesta parece ser que sí .
Código repetitivo:
#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;
}
Código para las pruebas reales:
#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 );
}
Ejecútalo here .
¿El estándar C ++ ofrece alguna garantía con respecto a este tema?
No que yo sepa. Sin embargo, diría que el estándar hace una recomendación implícita de no volver a crear el motor cada vez; para cualquier distribución, el prototipo de Distrib::operator() toma una referencia URNG& y no una referencia constante. Esto es comprensible, ya que es posible que el motor deba actualizar su estado interno, pero también implica que el código se vea así.
auto U = std::uniform_int_distribution(0,10);
for ( <something here> ) U(engine_type());
no compila, lo que para mí es un claro incentivo para no escribir código como este.
Estoy seguro de que hay muchos consejos sobre cómo utilizar correctamente la biblioteca aleatoria. Se complica si tiene que manejar la posibilidad de usar random_device s y permitir la siembra determinista para propósitos de prueba, pero pensé que podría ser útil lanzar mi propia recomendación también:
#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;
}
Ejecútalo here . ¡Espero que esto ayude!
EDITAR Mi primera recomendación fue un error, y me disculpo por eso; no podemos usar un motor singleton como en las pruebas anteriores, porque esto significaría que dos distribuciones int uniformes producirían la misma secuencia aleatoria. En cambio, confío en el hecho de que std::bind copia el motor recién creado localmente en std::function con su propia semilla, y esto produce el comportamiento esperado; Los diferentes generadores con la misma distribución producen diferentes secuencias aleatorias.