sirve - librerias dev c++ pdf

¿Por qué la nueva biblioteca aleatoria es mejor que std:: rand()?

Question

Así que vi una charla llamada rand () considerada dañina y recomendó el uso del paradigma de distribución de motores de la generación de números aleatorios sobre el paradigma simple std::rand() más módulo.

Sin embargo, quería ver las fallas de std::rand() primera mano, así que hice un experimento rápido:

1. Básicamente, escribí 2 funciones getRandNum_Old() y getRandNum_New() que generaron un número aleatorio entre 0 y 5 inclusive usando std::rand() y std::mt19937 + std::uniform_int_distribution respectivamente.
2. Luego generé 960,000 (divisibles por 6) números aleatorios usando la forma "antigua" y registré las frecuencias de los números 0-5. Entonces calculé la desviación estándar de estas frecuencias. Lo que estoy buscando es una desviación estándar lo más baja posible, ya que eso es lo que sucedería si la distribución fuera realmente uniforme.
3. Ejecuté esa simulación 1000 veces y registré la desviación estándar para cada simulación. También grabé el tiempo que tomó en milisegundos.
4. Después, hice exactamente lo mismo otra vez, pero esta vez generando números aleatorios de la manera "nueva".
5. Finalmente, calculé la media y la desviación estándar de la lista de desviaciones estándar para la forma antigua y nueva, y la media y la desviación estándar para la lista de tiempos tomados para la forma antigua y nueva.

Aquí fueron los resultados:

[OLD WAY]
Spread
       mean:  346.554406
    std dev:  110.318361
Time Taken (ms)
       mean:  6.662910
    std dev:  0.366301

[NEW WAY]
Spread
       mean:  350.346792
    std dev:  110.449190
Time Taken (ms)
       mean:  28.053907
    std dev:  0.654964

Sorprendentemente, la distribución agregada de rollos fue la misma para ambos métodos. Es decir, std::mt19937 + std::uniform_int_distribution no era "más uniforme" que el simple std::rand() + % . Otra observación que hice fue que el nuevo era 4 veces más lento que el antiguo. En general, parecía que estaba pagando un enorme costo en velocidad por casi ninguna ganancia en calidad.

¿Es mi experimento defectuoso de alguna manera? ¿O es que std::rand() realmente no es tan malo, y quizás incluso mejor?

Para referencia, aquí está el código que utilicé en su totalidad:

#include <cstdio>
#include <random>
#include <algorithm>
#include <chrono>

int getRandNum_Old() {
    static bool init = false;
    if (!init) {
        std::srand(time(nullptr)); // Seed std::rand
        init = true;
    }

    return std::rand() % 6;
}

int getRandNum_New() {
    static bool init = false;
    static std::random_device rd;
    static std::mt19937 eng;
    static std::uniform_int_distribution<int> dist(0,5);
    if (!init) {
        eng.seed(rd()); // Seed random engine
        init = true;
    }

    return dist(eng);
}

template <typename T>
double mean(T* data, int n) {
    double m = 0;
    std::for_each(data, data+n, [&](T x){ m += x; });
    m /= n;
    return m;
}

template <typename T>
double stdDev(T* data, int n) {
    double m = mean(data, n);
    double sd = 0.0;
    std::for_each(data, data+n, [&](T x){ sd += ((x-m) * (x-m)); });
    sd /= n;
    sd = sqrt(sd);
    return sd;
}

int main() {
    const int N = 960000; // Number of trials
    const int M = 1000;   // Number of simulations
    const int D = 6;      // Num sides on die

    /* Do the things the "old" way (blech) */

    int freqList_Old[D];
    double stdDevList_Old[M];
    double timeTakenList_Old[M];

    for (int j = 0; j < M; j++) {
        auto start = std::chrono::high_resolution_clock::now();
        std::fill_n(freqList_Old, D, 0);
        for (int i = 0; i < N; i++) {
            int roll = getRandNum_Old();
            freqList_Old[roll] += 1;
        }
        stdDevList_Old[j] = stdDev(freqList_Old, D);
        auto end = std::chrono::high_resolution_clock::now();
        auto dur = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
        double timeTaken = dur.count() / 1000.0;
        timeTakenList_Old[j] = timeTaken;
    }

    /* Do the things the cool new way! */

    int freqList_New[D];
    double stdDevList_New[M];
    double timeTakenList_New[M];

    for (int j = 0; j < M; j++) {
        auto start = std::chrono::high_resolution_clock::now();
        std::fill_n(freqList_New, D, 0);
        for (int i = 0; i < N; i++) {
            int roll = getRandNum_New();
            freqList_New[roll] += 1;
        }
        stdDevList_New[j] = stdDev(freqList_New, D);
        auto end = std::chrono::high_resolution_clock::now();
        auto dur = std::chrono::duration_cast<std::chrono::microseconds>(end-start);
        double timeTaken = dur.count() / 1000.0;
        timeTakenList_New[j] = timeTaken;
    }

    /* Display Results */

    printf("[OLD WAY]/n");
    printf("Spread/n");
    printf("       mean:  %.6f/n", mean(stdDevList_Old, M));
    printf("    std dev:  %.6f/n", stdDev(stdDevList_Old, M));
    printf("Time Taken (ms)/n");
    printf("       mean:  %.6f/n", mean(timeTakenList_Old, M));
    printf("    std dev:  %.6f/n", stdDev(timeTakenList_Old, M));
    printf("/n");
    printf("[NEW WAY]/n");
    printf("Spread/n");
    printf("       mean:  %.6f/n", mean(stdDevList_New, M));
    printf("    std dev:  %.6f/n", stdDev(stdDevList_New, M));
    printf("Time Taken (ms)/n");
    printf("       mean:  %.6f/n", mean(timeTakenList_New, M));
    printf("    std dev:  %.6f/n", stdDev(timeTakenList_New, M));
}

Answer 1

La respuesta correcta es: depende de lo que quiere decir con "mejor".

Los "nuevos" motores <random> se introdujeron en C ++ hace más de 13 años, por lo que no son realmente nuevos. El rand() biblioteca de C rand() se introdujo hace décadas y ha sido muy útil en ese tiempo para cualquier número de cosas.

La biblioteca estándar de C ++ proporciona tres clases de motores generadores de números aleatorios: el congruente lineal (de los cuales rand() es un ejemplo), el Fibonacci desfasado y el Twister de Mersenne. Hay concesiones de cada clase, y cada clase es "mejor" de ciertas maneras. Por ejemplo, los LCG tienen un estado muy pequeño y, si se eligen los parámetros correctos, bastante rápido en los procesadores de escritorio modernos. Los LFG tienen un estado más grande y utilizan solo operaciones de recuperación y recuperación de memoria, por lo que son muy rápidos en sistemas integrados y microcontroladores que carecen de hardware matemático especializado. El MTG tiene un estado enorme y es lento, pero puede tener una secuencia no repetitiva muy grande con excelentes características espectrales.

Si ninguno de los generadores suministrados es lo suficientemente bueno para su uso específico, la biblioteca estándar de C ++ también proporciona una interfaz para un generador de hardware o su propio motor personalizado. Ninguno de los generadores está diseñado para ser utilizado de forma independiente: su uso previsto es a través de un objeto de distribución que proporciona una secuencia aleatoria con una función de distribución de probabilidad particular.

Otra ventaja de <random> sobre rand() es que rand() usa el estado global, no es reentrante ni seguro para subprocesos, y permite una sola instancia por proceso. Si necesita un control preciso o una previsibilidad (es decir, poder reproducir un error dado el estado de inicio de RNG), rand() sirve para nada. Los generadores <random> instalan localmente y tienen un estado serializable (y restaurable).

Answer 2

Prácticamente cualquier implementación de "antiguo" rand() usa un LCG ; Si bien generalmente no son los mejores generadores del mercado, por lo general no los verá fallar en una prueba tan básica. La media y la desviación estándar generalmente se corrigen incluso en los peores PRNG.

Las fallas comunes de las implementaciones "malas", pero lo suficientemente comunes, rand() son:

• baja aleatoriedad de bits de orden inferior;
• período corto;
• bajo RAND_MAX ;
• alguna correlación entre extracciones sucesivas (en general, las LCG producen números que se encuentran en un número limitado de hiperplanos, aunque esto puede mitigarse de alguna manera).

Aún así, ninguno de estos son específicos de la API de rand() . Una implementación particular podría colocar un generador de la familia xorshift detrás de srand / rand y, algoritmicamente hablando, obtener un PRNG de vanguardia sin cambios de interfaz, por lo que ninguna prueba como la que hiciste mostraría alguna debilidad en la salida.

Edición: @R. observa correctamente que la interfaz rand / srand está limitada por el hecho de que srand toma un unsigned int , por lo que cualquier generador que una implementación pueda poner detrás de él está intrínsecamente limitado a UINT_MAX posibles semillas iniciales UINT_MAX (y, por lo tanto, a las secuencias generadas). De hecho, esto es cierto, aunque la API podría ampliarse trivialmente para hacer que srand tome un unsigned long long , o agregando una sobrecarga de srand(unsigned char *, size_t) separado.

De hecho, el problema real con rand() no es mucho de implementación en principio, pero:

• compatibilidad al revés; muchas implementaciones actuales usan generadores subóptimos, típicamente con parámetros mal elegidos; un ejemplo notorio es Visual C ++, que tiene un RAND_MAX de solo 32767. Sin embargo, esto no se puede cambiar fácilmente, ya que rompería la compatibilidad con el pasado; las personas que usan srand con una semilla fija para simulaciones reproducibles no serían muy felices (de hecho, , IIRC la implementación mencionada se remonta a las versiones anteriores de Microsoft C, o incluso a Lattice C, desde mediados de los años ochenta;

• interfaz simplista; rand() proporciona un único generador con el estado global para todo el programa. Si bien esto está perfectamente bien (y en realidad es bastante útil) para muchos casos de uso simples, plantea problemas:

  • con código multiproceso: para solucionarlo, o bien necesita un mutex global, que ralentizaría todo sin motivo y eliminaría cualquier posibilidad de repetición, ya que la secuencia de llamadas se vuelve aleatoria en sí misma, o estado de subproceso local; esta última ha sido adoptada por varias implementaciones (notablemente Visual C ++);
  • si desea una secuencia "privada" y reproducible en un módulo específico de su programa que no afecte el estado global.

Finalmente, el estado de cosas del rand :

• no especifica una implementación real (el estándar C proporciona solo una implementación de muestra), por lo que cualquier programa que tenga la intención de producir resultados reproducibles (o esperar un PRNG de alguna calidad conocida) entre compiladores diferentes debe utilizar su propio generador;
• no proporciona ningún método multiplataforma para obtener una semilla decente (el time(NULL) no lo es, ya que no es lo suficientemente granular y, a menudo, piense en dispositivos integrados sin RTC, ni siquiera lo suficientemente aleatorios).

Por lo tanto, el nuevo encabezado <random> , que intenta arreglar este lío, proporciona algoritmos que son:

• totalmente especificado (para que pueda tener una salida reproducible de compilador cruzado y características garantizadas, por ejemplo, rango del generador);
• generalmente de calidad de vanguardia ( desde el momento en que se diseñó la biblioteca ; consulte más abajo);
• encapsulado en clases (por lo que no se le impone ningún estado global, lo que evita problemas de subprocesos y problemas de ubicación);

... y un random_device defecto también para random_device .

Ahora, si me preguntas, me hubiera gustado también una API simple construida sobre esto para los casos "fáciles", "adivina un número" (similar a cómo Python proporciona la API "complicada", pero también el random.randint trivial random.randint & Co. utiliza un PRNG global pre sembrado para nosotros, personas sin complicaciones que no quisieran ahogarse en dispositivos aleatorios / motores / adaptadores / lo que sea cada vez que queramos extraer un número para las tarjetas de bingo), pero es cierto usted puede construirlo fácilmente por sí mismo sobre las instalaciones actuales (mientras que construir la API "completa" sobre una simplista no sería posible).

Finalmente, para volver a su comparación de rendimiento: como han especificado otros, está comparando un LCG rápido con un Mersenne Twister más lento (pero generalmente considerado de mejor calidad); Si está de acuerdo con la calidad de una LCG, puede usar std::minstd_rand lugar de std::mt19937 .

De hecho, después de ajustar su función para usar std::minstd_rand y evitar variables estáticas inútiles para la inicialización

int getRandNum_New() {
    static std::minstd_rand eng{std::random_device{}()};
    static std::uniform_int_distribution<int> dist{0, 5};
    return dist(eng);
}

Tengo 9 ms (antiguo) vs 21 ms (nuevo); finalmente, si me deshago de dist (que, en comparación con el operador de módulo clásico, maneja el sesgo de distribución para el rango de salida no múltiple del rango de entrada) y vuelvo a lo que está haciendo en getRandNum_Old()

int getRandNum_New() {
    static std::minstd_rand eng{std::random_device{}()};
    return eng() % 6;
}

Lo reduzco a 6 ms (es decir, un 30% más rápido), probablemente porque, a diferencia de la llamada a rand() , std::minstd_rand es más fácil en línea.

Incidentalmente, hice la misma prueba con un XorShift64* enrollado a mano (pero bastante XorShift64* a la interfaz de la biblioteca estándar), y es 2.3 veces más rápido que rand() (3.68 ms frente a 8.61 ms); dado que, a diferencia de Mersenne Twister y los diversos LCG proporcionados, pasa las pruebas de aleatoriedad actuales con gran éxito y es increíblemente rápido, por lo que se pregunta por qué aún no está incluido en la biblioteca estándar.

Answer 3

Primero, sorprendentemente, la respuesta cambia dependiendo de para qué está utilizando el número aleatorio. Si se trata de conducir, digamos, un cambiador de color de fondo aleatorio, utilizando rand () es perfectamente correcto. Si está utilizando un número aleatorio para crear una mano de póquer aleatoria o una clave segura criptográficamente, entonces no está bien.

Previsibilidad: la secuencia 012345012345012345012345 ... proporcionaría una distribución uniforme de cada número en su muestra, pero obviamente no es aleatoria. Para que una secuencia sea aleatoria, el valor de n + 1 no se puede predecir fácilmente por el valor de n (o incluso por los valores de n, n-1, n-2, n-3, etc.) Claramente una secuencia repetitiva de los mismos dígitos es un caso degenerado, pero una secuencia generada con cualquier generador lineal congruente puede someterse a análisis; Si usa la configuración predeterminada lista para usar de un LCG común de una biblioteca común, una persona maliciosa podría "romper la secuencia" sin mucho esfuerzo. En el pasado, varios casinos en línea (y algunos de ladrillo y mortero) fueron golpeados por pérdidas por máquinas que utilizan pobres generadores de números aleatorios. Incluso las personas que deberían saber mejor han sido atrapadas; Se ha demostrado que los chips TPM de varios fabricantes son más fáciles de romper que lo que predeciría la longitud de bits de las claves debido a las malas elecciones realizadas con los parámetros de generación de claves.

Distribución: Como se menciona en el video, tomar un módulo de 100 (o cualquier valor que no sea divisible en la longitud de la secuencia) garantizará que algunos resultados serán al menos ligeramente más probables que otros resultados. En el universo de 32767 posibles valores iniciales, módulo 100, los números 0 a 66 aparecerán 328/327 (0,3%) con mayor frecuencia que los valores 67 a 99; un factor que puede proporcionar una ventaja a un atacante.

Answer 4

Si repite el experimento con un rango superior a 5, es probable que vea resultados diferentes. Cuando su rango es significativamente menor que RAND_MAX no hay un problema para la mayoría de las aplicaciones.

Por ejemplo, si tenemos un RAND_MAX de 25, rand() % 5 producirá números con las siguientes frecuencias:

0: 6
1: 5
2: 5
3: 5
4: 5

Como RAND_MAX tiene una garantía de más de 32767 y la diferencia en las frecuencias entre las menos probables y las más probables es solo 1, para pequeños números la distribución es lo suficientemente aleatoria para la mayoría de los casos de uso.