c++ - vehicle - Diferencias de motor aleatorias

tag renewal online

Question

El estándar C ++ 11 especifica una serie de motores diferentes para la generación de números aleatorios: linear_congruential_engine , linear_congruential_engine , linear_congruential_engine y así sucesivamente. Obviamente, este es un gran cambio con respecto al antiguo uso de std::rand .

Obviamente, uno de los principales beneficios de (al menos algunos) de estos motores es la longitud de período enormemente aumentada (está integrada en el nombre de std::mt19937 ).

Sin embargo, las diferencias entre los motores son menos claras. ¿Cuáles son las fortalezas y debilidades de los diferentes motores? ¿Cuándo se debe usar uno sobre el otro? ¿Hay un error razonable que generalmente debería ser preferido?

Answer 1

Acabo de ver esta respuesta de Marnos y decidí probarla yo mismo. std::chono::high_resolution_clock para std::chono::high_resolution_clock 100000 muestras 100 veces para generar un promedio. Medí todo en std::chrono::nanoseconds y terminé con diferentes resultados:

std::minstd_rand tuvo un promedio de 28991658 nanosegundos

std::mt19937 tenía un promedio de 29871710 nanosegundos

ranlux48_base tuvo un promedio de 29281677 nanosegundos

Esto está en una máquina con Windows 7. El compilador es Mingw-Builds 4.8.1 64bit. Obviamente, esto está usando el indicador C ++ 11 y no hay indicadores de optimización.

Cuando -O3 optimizaciones de std::minstd_rand , std::minstd_rand y ranlux48_base realmente se ejecutan más rápido de lo que la implementación de high_precision_clock puede medir; sin embargo, std::mt19937 aún tarda 730045 nanosegundos, o 3/4 de segundo.

Entonces, como dijo, es específico de la implementación, pero al menos en GCC, el tiempo promedio parece ajustarse a lo que dicen las descripciones en la respuesta aceptada. Mersenne Twister parece beneficiarse menos de las optimizaciones, mientras que los otros dos simplemente arrojan los números aleatorios increíblemente rápido una vez que se tienen en cuenta las optimizaciones del compilador.

Por otro lado, he estado usando el motor Mersenne Twister en mi biblioteca de generación de ruido (no precalcula gradientes), así que creo que cambiaré a uno de los otros para ver realmente algunas mejoras de velocidad. En mi caso, la aleatoriedad "verdadera" no importa.

Código:

#include <iostream>
#include <chrono>
#include <random>
using namespace std;
using namespace std::chrono;
int main()
{
minstd_rand linearCongruentialEngine;
mt19937 mersenneTwister;
ranlux48_base subtractWithCarry;
uniform_real_distribution<float> distro;
int numSamples = 100000;
int repeats = 100;
long long int avgL = 0;
long long int avgM = 0;
long long int avgS = 0;
cout << "results:" << endl;
for(int j = 0; j < repeats; ++j)
{
cout << "start of sequence: " << j << endl;
auto start = high_resolution_clock::now();
for(int i = 0; i < numSamples; ++i)
distro(linearCongruentialEngine);
auto stop = high_resolution_clock::now();
auto L = duration_cast<nanoseconds>(stop-start).count();
avgL += L;
cout << "Linear Congruential:/t" << L << endl;
start = high_resolution_clock::now();
for(int i = 0; i < numSamples; ++i)
distro(mersenneTwister);
stop = high_resolution_clock::now();
auto M = duration_cast<nanoseconds>(stop-start).count();
avgM += M;
cout << "Mersenne Twister:/t" << M << endl;
start = high_resolution_clock::now();
for(int i = 0; i < numSamples; ++i)
distro(subtractWithCarry);
stop = high_resolution_clock::now();
auto S = duration_cast<nanoseconds>(stop-start).count();
avgS += S;
cout << "Subtract With Carry:/t" << S << endl;
}
cout << setprecision(10) << "/naverage:/nLinear Congruential: " << (long double)(avgL/repeats)
<< "/nMersenne Twister: " << (long double)(avgM/repeats)
<< "/nSubtract with Carry: " << (long double)(avgS/repeats) << endl;
}

Answer 2

Como las otras respuestas se olvidan del reflujo, aquí hay una pequeña nota de un desarrollador de AMD que recientemente la ha portado a OpenCL:

https://community.amd.com/thread/139236

RANLUX es también uno de los pocos (el único que conozco en realidad) PRNG que tiene una teoría subyacente que explica por qué genera números "aleatorios" y por qué son buenos. De hecho, si la teoría es correcta (y no conozco a nadie que la haya disputado), RANLUX en el nivel más alto de lujo produce números completamente descorrelacionados hasta el último bit, sin correlaciones de largo alcance, siempre y cuando nos mantengamos bien debajo del período (10 ^ 171). La mayoría de los otros generadores pueden decir muy poco acerca de su calidad (como Mersenne Twister, KISS, etc.). Deben confiar en pasar las pruebas estadísticas.

Los físicos del CERN son admiradores de este PRNG. ''dijo nuff.

Answer 3

Creo que el punto es que los generadores aleatorios tienen propiedades diferentes, que pueden hacerlos más adecuados o no para un problema determinado.

• La duración del período es una de las propiedades.
• La calidad de los números aleatorios también puede ser importante.
• El rendimiento del generador también puede ser un problema.

Dependiendo de su necesidad, puede tomar un generador u otro. Por ejemplo, si necesita números aleatorios rápidos pero realmente no le importa la calidad, un LCG podría ser una buena opción. Si desea números aleatorios de mejor calidad, el Mersenne Twister es probablemente una mejor opción.

Para ayudarlo a hacer su elección, hay algunas pruebas estándar y resultados (definitivamente me gusta la tabla p.29 de este documento ).

EDITAR: Del papel,

1. La familia LCG ( LCG(***) en el papel) son los generadores más rápidos, pero con la calidad más pobre.
2. El Mersenne Twister ( MT19937 ) es un poco más lento, pero produce mejores números aleatorios.
3. El extracto con acarreo ( SWB(***) , creo) es mucho más lento, pero puede producir mejores propiedades aleatorias cuando está bien ajustado.

Answer 4

De las explicaciones a continuación, el motor lineal parece ser más rápido pero menos aleatorio, mientras que Marsenne Twister tiene una mayor complejidad y aleatoriedad. El motor de números aleatorios de restar con carga es una mejora para el motor lineal y es definitivamente más aleatorio. En la última referencia, se afirma que Mersenne Twister tiene mayor complejidad que el motor de número aleatorio de restar con carga

Motor de número aleatorio congruente lineal

Un generador de números pseudoaleatorio que produce números enteros sin signo.

Este es el motor de generador más simple en la biblioteca estándar. Su estado es un único valor entero, con el siguiente algoritmo de transición:

x = (ax + c) mod m

Donde x es el valor de estado actual, a y c son sus respectivos parámetros de plantilla, ym es su parámetro de plantilla respectivo si esto es mayor que 0, o numerics_limits :: max () más 1, de lo contrario.

Su algoritmo de generación es una copia directa del valor del estado.

Esto lo convierte en un generador extremadamente eficiente en términos de procesamiento y consumo de memoria, pero produce números con diversos grados de correlación serial, dependiendo de los parámetros específicos utilizados.

Los números aleatorios generados por linear_congruential_engine tienen un período de m. http://www.cplusplus.com/reference/random/linear_congruential_engine/

Mersenne twister motor de número aleatorio

Un motor de generador de números pseudoaleatorio que produce números enteros sin signo en el intervalo cerrado [0,2 ^ w-1].

El algoritmo utilizado por este motor está optimizado para calcular grandes series de números (como en los experimentos de Monte Carlo) con una distribución casi uniforme en el rango.

El motor tiene una secuencia de estado interno de n elementos enteros, que se llena con una serie pseudoaleatoria generada en la construcción o llamando a la semilla de la función miembro.

La secuencia de estado interna se convierte en la fuente de n elementos: cuando el estado avanza (por ejemplo, para producir un nuevo número aleatorio), el motor altera la secuencia de estado al girar el valor actual utilizando xor mask a en una combinación de bits determinado por el parámetro r que proviene de ese valor y de un valor de m elementos de distancia (ver operador () para más detalles).

Los números aleatorios producidos son versiones templadas de estos valores retorcidos. El templado es una secuencia de operaciones de desplazamiento y xor definidas por los parámetros u, d, s, b, t, c y l aplicados en el valor de estado seleccionado (ver operador ()).

Los números aleatorios generados por mersenne_twister_engine tienen un período equivalente al número 2 de mersenne ((n-1) * w) -1. http://www.cplusplus.com/reference/random/mersenne_twister_engine/

Restar-con-llevar motor de número aleatorio

Un generador de números pseudoaleatorio que produce números enteros sin signo.

El algoritmo utilizado por este motor es un generador de fibonacci rezagado, con una secuencia de estado de r elementos enteros, más un valor de acarreo. http://www.cplusplus.com/reference/random/subtract_with_carry_engine/

Los generadores de Fibonacci retardados tienen un período máximo de (2k - 1) * ^ (2M-1) si se usa la suma o la resta. La inicialización de biogás es un problema muy complejo. La producción de biogás es muy sensible a las condiciones iniciales, y los defectos estadísticos pueden aparecer inicialmente pero también periódicamente en la secuencia de salida, a menos que se tenga extremo cuidado. Otro problema potencial con los biogás es que la teoría matemática detrás de ellos es incompleta, por lo que es necesario confiar en las pruebas estadísticas en lugar del rendimiento teórico. http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

Y finalmente: la elección de qué motor utilizar implica una serie de ventajas y desventajas: el motor congruente lineal es moderadamente rápido y tiene un requisito de almacenamiento muy pequeño para el estado. Los generadores de Fibonacci rezagados son muy rápidos incluso en procesadores sin conjuntos de instrucciones aritméticas avanzadas, a expensas de un mayor almacenamiento de estado y, a veces, características espectrales menos deseables. El tornado Mersenne es más lento y tiene mayores requisitos de almacenamiento de estado, pero con los parámetros correctos tiene la secuencia no repetitiva más larga con las características espectrales más deseables (para una definición dada de deseable). en http://en.cppreference.com/w/cpp/numeric/random

Answer 5

En general, mersenne twister es el mejor (y más rápido) RNG, pero requiere algo de espacio (alrededor de 2,5 kilobytes). Cuál se adapta a su necesidad depende de cuántas veces necesite crear una instancia del objeto generador. (Si necesita instanciarlo solo una vez, o algunas veces, MT es el que debe usar. Si necesita instanciarlo millones de veces, quizás algo más pequeño).

Algunas personas informan que MT es más lento que algunos de los demás. De acuerdo con mis experimentos, esto depende mucho de la configuración de optimización del compilador. Lo más importante es que la configuración -march = native puede hacer una gran diferencia, dependiendo de la arquitectura de su host.

Ejecuté un pequeño programa para probar la velocidad de diferentes generadores y sus tamaños, y obtuve esto:

std::mt19937 (2504 bytes): 1.4714 s
std::mt19937_64 (2504 bytes): 1.50923 s
std::ranlux24 (120 bytes): 16.4865 s
std::ranlux48 (120 bytes): 57.7741 s
std::minstd_rand (4 bytes): 1.04819 s
std::minstd_rand0 (4 bytes): 1.33398 s
std::knuth_b (1032 bytes): 1.42746 s

Answer 6

Es un compromiso realmente. Un PRNG como Mersenne Twister es mejor porque tiene un período extremadamente grande y otras buenas propiedades estadísticas.

Pero un PRNG de período grande ocupa más memoria (para mantener el estado interno) y también toma más tiempo para generar un número aleatorio (debido a las complejas transiciones y el procesamiento posterior).

Elija un PNRG según las necesidades de su aplicación. En caso de duda utilice Mersenne Twister , es el valor predeterminado en muchas herramientas.

Answer 7

Parte de la información en estas otras respuestas entra en conflicto con mis hallazgos. He realizado pruebas en Windows 8.1 usando Visual Studio 2013, y consistentemente he encontrado que mersenne_twister_engine es de mayor calidad y significativamente más rápido que linear_congruential_engine o linear_congruential_engine . Esto me lleva a creer, cuando se tiene en cuenta la información en las otras respuestas, que la implementación específica de un motor tiene un impacto significativo en el rendimiento.

Esto es una gran sorpresa para nadie, estoy seguro, pero no se menciona en las otras respuestas donde se dice que mersenne_twister_engine es más lento. No tengo resultados de prueba para otras plataformas y compiladores, pero con mi configuración, mersenne_twister_engine es claramente la elección superior cuando se considera el período, la calidad y el rendimiento de la velocidad. No he perfilado el uso de la memoria, por lo que no puedo hablar con la propiedad de requisito de espacio.

Aquí está el código que estoy usando para probar (para hacer portátil, solo debería tener que reemplazar las llamadas a la API de windows.h QueryPerformanceXxx() con un mecanismo de temporización apropiado):

// compile with: cl.exe /EHsc
#include <random>
#include <iostream>
#include <windows.h>
using namespace std;
void test_lc(const int a, const int b, const int s) {
/*
typedef linear_congruential_engine<unsigned int, 48271, 0, 2147483647> minstd_rand;
*/
minstd_rand gen(1729);
uniform_int_distribution<> distr(a, b);
for (int i = 0; i < s; ++i) {
distr(gen);
}
}
void test_mt(const int a, const int b, const int s) {
/*
typedef mersenne_twister_engine<unsigned int, 32, 624, 397,
31, 0x9908b0df,
11, 0xffffffff,
7, 0x9d2c5680,
15, 0xefc60000,
18, 1812433253> mt19937;
*/
mt19937 gen(1729);
uniform_int_distribution<> distr(a, b);
for (int i = 0; i < s; ++i) {
distr(gen);
}
}
void test_swc(const int a, const int b, const int s) {
/*
typedef subtract_with_carry_engine<unsigned int, 24, 10, 24> ranlux24_base;
*/
ranlux24_base gen(1729);
uniform_int_distribution<> distr(a, b);
for (int i = 0; i < s; ++i) {
distr(gen);
}
}
int main()
{
int a_dist = 0;
int b_dist = 1000;
int samples = 100000000;
cout << "Testing with " << samples << " samples." << endl;
LARGE_INTEGER ElapsedTime;
double ElapsedSeconds = 0;
LARGE_INTEGER Frequency;
QueryPerformanceFrequency(&Frequency);
double TickInterval = 1.0 / ((double) Frequency.QuadPart);
LARGE_INTEGER StartingTime;
LARGE_INTEGER EndingTime;
QueryPerformanceCounter(&StartingTime);
test_lc(a_dist, b_dist, samples);
QueryPerformanceCounter(&EndingTime);
ElapsedTime.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;
ElapsedSeconds = ElapsedTime.QuadPart * TickInterval;
cout << "linear_congruential_engine time: " << ElapsedSeconds << endl;
QueryPerformanceCounter(&StartingTime);
test_mt(a_dist, b_dist, samples);
QueryPerformanceCounter(&EndingTime);
ElapsedTime.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;
ElapsedSeconds = ElapsedTime.QuadPart * TickInterval;
cout << " mersenne_twister_engine time: " << ElapsedSeconds << endl;
QueryPerformanceCounter(&StartingTime);
test_swc(a_dist, b_dist, samples);
QueryPerformanceCounter(&EndingTime);
ElapsedTime.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;
ElapsedSeconds = ElapsedTime.QuadPart * TickInterval;
cout << "subtract_with_carry_engine time: " << ElapsedSeconds << endl;
}

Salida:

Testing with 100000000 samples. linear_congruential_engine time: 10.0821 mersenne_twister_engine time: 6.11615 subtract_with_carry_engine time: 9.26676