c++ - rango - generar numeros aleatorios en java sin repetir

Generar entero aleatorio de un rango

Question

Necesito una función que generaría un entero aleatorio en un rango dado (incluidos los valores de frontera). No tengo requisitos irracionales de calidad / aleatoriedad, tengo cuatro requisitos:

• Necesito que sea rápido. Mi proyecto necesita generar millones (o incluso decenas de millones) de números aleatorios y mi función de generador actual ha demostrado ser un cuello de botella.
• Necesito que sea razonablemente uniforme (el uso de rand () está perfectamente bien).
• los rangos min-max pueden ser cualquier cosa desde <0, 1> a <-32727, 32727>.
• tiene que ser visible

Actualmente tengo el siguiente código de C ++:

output = min + (rand() * (int)(max - min) / RAND_MAX)

El problema es que no es realmente uniforme: max se devuelve solo cuando rand () = RAND_MAX (para Visual C ++ es 1/32727). Este es un problema importante para rangos pequeños como <-1, 1>, donde casi nunca se devuelve el último valor.

Así que agarré lápiz y papel y se me ocurrió la siguiente fórmula (que se basa en el truco de redondeo entero (int) (n + 0.5)):

Pero todavía no me da una distribución uniforme. Las ejecuciones repetidas con 10000 muestras dan una proporción de 37:50:13 para valores de valores -1, 0. 1.

¿Podría sugerir una mejor fórmula? (o incluso toda la función del generador de números pseudoaleatorio)

Answer 1

¿Qué tal el Mersenne Twister ? La implementación de impulso es bastante fácil de usar y está bien probada en muchas aplicaciones del mundo real. Lo he usado yo mismo en varios proyectos académicos, como inteligencia artificial y algoritmos evolutivos.

Aquí está su ejemplo donde hacen una función simple para lanzar un dado de seis caras:

#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>

boost::mt19937 gen;

int roll_die() {
    boost::uniform_int<> dist(1, 6);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> > die(gen, dist);
    return die();
}

Ah, y aquí hay un poco de proxenetismo de este generador por si acaso no está convencido de que debería usarlo sobre el rand() inmensamente inferior rand() :

El Mersenne Twister es un generador de "números aleatorios" inventado por Makoto Matsumoto y Takuji Nishimura; su sitio web incluye numerosas implementaciones del algoritmo.

Esencialmente, el Mersenne Twister es un registro de desplazamiento de retroalimentación lineal muy grande. El algoritmo opera en una semilla de 19,937 bits, almacenada en una matriz de 624 elementos de enteros sin signo de 32 bits. El valor 2 ^ 19937-1 es un primo de Mersenne; la técnica para manipular la semilla se basa en un antiguo algoritmo de "torsión", de ahí el nombre "Mersenne Twister".

Un aspecto atractivo del Mersenne Twister es su uso de operaciones binarias, en oposición a la multiplicación que consume mucho tiempo, para generar números. El algoritmo también tiene un período muy largo y buena granularidad. Es rápido y efectivo para aplicaciones no criptográficas.

Answer 2

Aquí hay una versión imparcial que genera números en [low, high] :

int r;
do {
  r = rand();
} while (r < ((unsigned int)(RAND_MAX) + 1) % (high + 1 - low));
return r % (high + 1 - low) + low;

Si su rango es razonablemente pequeño, no hay razón para almacenar el lado derecho de la comparación en el bucle do .

Answer 3

En este tema, el muestreo de rechazo ya fue discutido, pero quería sugerir una optimización basada en el hecho de que rand() % 2^something no introduce ningún sesgo como ya se mencionó anteriormente.

El algoritmo es realmente simple:

• calcule la potencia más pequeña de 2 mayor que la longitud del intervalo
• aleatorizar un número en ese "nuevo" intervalo
• devuelve ese número si es menor que la longitud del intervalo original
  • rechazar de otra manera

Aquí está mi código de muestra:

int randInInterval(int min, int max) {
    int intervalLen = max - min + 1;
    //now calculate the smallest power of 2 that is >= than `intervalLen`
    int ceilingPowerOf2 = pow(2, ceil(log2(intervalLen)));

    int randomNumber = rand() % ceilingPowerOf2; //this is "as uniform as rand()"

    if (randomNumber < intervalLen)
        return min + randomNumber;      //ok!
    return randInInterval(min, max);    //reject sample and try again
} 

Esto funciona bien especialmente para intervalos pequeños, porque la potencia de 2 estará "más cerca" de la longitud del intervalo real, por lo que el número de errores será menor.

PD
Obviamente, evitar la recursividad sería más eficiente (no es necesario calcular una y otra vez el techo del registro), pero pensé que era más legible para este ejemplo.

Answer 4

La fórmula para esto es muy simple, así que prueba esta expresión,

 int num = (int) rand() % (max - min) + min;  
 //Where rand() returns a random number between 0.0 and 1.0

Answer 5

La respuesta más simple (y por lo tanto mejor) a C ++ (usando el estándar 2011) es

#include <random>

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

No hay necesidad de reinventar la rueda. No hay necesidad de preocuparse por el sesgo. No hay necesidad de preocuparse por usar el tiempo como semilla aleatoria.

Answer 6

La siguiente expresión debería ser imparcial si no me equivoco:

std::floor( ( max - min + 1.0 ) * rand() ) + min;

Estoy asumiendo aquí que rand () te da un valor aleatorio en el rango entre 0.0 y 1.0 que NO incluye 1.0 y que max y min son enteros con la condición de que min <max.

Answer 7

Recomiendo la Boost.Random , es súper detallada y está bien documentada, le permite especificar de manera explícita qué distribución desea, y en escenarios no criptográficos puede outperform típica implementación de rand de la biblioteca C.

Answer 8

Si su compilador admite C ++ 0x y usarlo es una opción para usted, entonces es probable que el nuevo encabezado <random> estándar satisfaga sus necesidades. Tiene una uniform_int_distribution alta calidad que aceptará límites mínimos y máximos (todo lo que necesite), y puede elegir entre varios generadores de números aleatorios para conectarse a esa distribución.

Aquí hay un código que genera un millón de int aleatorios distribuidos uniformemente en [-57, 365]. He utilizado las nuevas instalaciones estándar <chrono> para cronometrarlo, ya que mencionas que el rendimiento es una gran preocupación para ti.

#include <iostream>
#include <random>
#include <chrono>

int main()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::duration<double> sec;
    Clock::time_point t0 = Clock::now();
    const int N = 10000000;
    typedef std::minstd_rand G;
    G g;
    typedef std::uniform_int_distribution<> D;
    D d(-57, 365);
    int c = 0;
    for (int i = 0; i < N; ++i) 
        c += d(g);
    Clock::time_point t1 = Clock::now();
    std::cout << N/sec(t1-t0).count() << " random numbers per second./n";
    return c;
}

Para mí (2.8 GHz Intel Core i5) esto se imprime:

2.10268e + 07 números aleatorios por segundo.

Puedes sembrar el generador pasando un int a su constructor:

    G g(seed);

Si luego encuentra que int no cubre el rango que necesita para su distribución, esto puede remediarse cambiando la uniform_int_distribution como tal (por ejemplo, long long ):

    typedef std::uniform_int_distribution<long long> D;

Si luego encuentra que el minstd_rand no es un generador de calidad lo suficientemente alta, también puede minstd_rand fácilmente. P.ej:

    typedef std::mt19937 G;  // Now using mersenne_twister_engine

Tener un control separado sobre el generador de números aleatorios, y la distribución aleatoria puede ser bastante liberador.

También he calculado (no mostrado) los primeros 4 "momentos" de esta distribución (usando minstd_rand ) y los minstd_rand con los valores teóricos en un intento de cuantificar la calidad de la distribución:

min = -57
max = 365
mean = 154.131
x_mean = 154
var = 14931.9
x_var = 14910.7
skew = -0.00197375
x_skew = 0
kurtosis = -1.20129
x_kurtosis = -1.20001

(El prefijo x_ refiere a "esperado")

Answer 9

Una solución distribuida rápida, algo mejor que la tuya, pero aún no es la adecuada

output = min + (rand() % static_cast<int>(max - min + 1))

Excepto cuando el tamaño del rango es una potencia de 2, este método produce números distribuidos no uniformes y sesgados independientemente de la calidad de rand() . Para una prueba completa de la calidad de este método, lea esto .

Answer 10

Vamos a dividir el problema en dos partes:

• Genere un número aleatorio n en el rango de 0 a (máximo-mínimo).
• Agrega un mínimo a ese número

La primera parte es obviamente la más difícil. Supongamos que el valor de retorno de rand () es perfectamente uniforme. El uso de módulo agregará sesgo a los primeros números (RAND_MAX + 1) % (max-min+1) . Entonces, si pudiéramos cambiar mágicamente RAND_MAX a RAND_MAX - (RAND_MAX + 1) % (max-min+1) , ya no existiría ningún sesgo.

Resulta que podemos usar esta intuición si estamos dispuestos a permitir el pseudo-no-determinismo en el tiempo de ejecución de nuestro algoritmo. Cuando rand () devuelve un número que es demasiado grande, simplemente solicitamos otro número aleatorio hasta que obtengamos uno que sea lo suficientemente pequeño.

El tiempo de ejecución ahora está distribuido geométricamente , con el valor esperado 1/p donde p es la probabilidad de obtener un número suficientemente pequeño en el primer intento. Como RAND_MAX - (RAND_MAX + 1) % (max-min+1) siempre es menor que (RAND_MAX + 1) / 2 , sabemos que p > 1/2 , por lo que el número esperado de iteraciones siempre será menor que dos para cualquier rango Debería ser posible generar decenas de millones de números aleatorios en menos de un segundo en una CPU estándar con esta técnica.

EDITAR:

Aunque lo anterior es técnicamente correcto, la respuesta de DSimon es probablemente más útil en la práctica. No deberías implementar esto tú mismo. He visto muchas implementaciones de muestreo de rechazo y a menudo es muy difícil ver si es correcto o no.

Answer 11

supongamos que min y max son valores int, [y] significa que incluyen este valor, (y) significa que no incluyen este valor, usando arriba para obtener el valor correcto usando c ++ rand ()

referencia: para () [] definir, visitar:

https://en.wikipedia.org/wiki/Interval_(mathematics)

para la función rand y srand o RAND_MAX define, visita:

http://en.cppreference.com/w/cpp/numeric/random/rand

[mínimo máximo]

int randNum = rand() % (max - min + 1) + min

(mínimo máximo]

int randNum = rand() % (max - min) + min + 1

[mínimo máximo)

int randNum = rand() % (max - min) + min

(mínimo máximo)

int randNum = rand() % (max - min - 1) + min + 1

Answer 12

int RandU(int nMin, int nMax)
{
    return nMin + (int)((double)rand() / (RAND_MAX+1) * (nMax-nMin+1));
}

Este es un mapeo de enteros 32768 a enteros (nMax-nMin + 1). El mapeo será bastante bueno si (nMax-nMin + 1) es pequeño (como en su requerimiento). Sin embargo, tenga en cuenta que si (nMax-nMin + 1) es grande, la asignación no funcionará (por ejemplo, no puede asignar 32768 valores a 30000 valores con la misma probabilidad). Si se necesitan tales rangos, debe usar una fuente aleatoria de 32 o 64 bits, en lugar de los resultados de rand () de 15 bits o ignorar los resultados de rand () que están fuera del rango.