rango - generar numeros aleatorios en c++ sin repetir
Necesita un generador aleatorio rápido para c++ (10)
¿puedes pregenerar un montón de bits aleatorios con anticipación y pelarlos de a 2 por vez (ya que solo necesitas un número aleatorio entre 1 y 3)?
Estoy intentando hacer un intercambio de opt-3 en mi generador de TSP para distancias euclidianas, y como en muchos casos tengo más de ~ 500 nodos, necesito seleccionar aleatoriamente al menos 1 de los 3 nodos que deseo probar intercambiando .
Entonces, básicamente, necesito una función de números aleatorios que sea rápida . (el rand normal () es demasiado lento) No tiene que ser increíble, solo lo suficientemente bueno.
EDITAR: Olvidé mencionar que estoy sentado en un entorno en el que no puedo agregar ninguna biblioteca excepto la biblioteca de idioma estándar (como STL, iostream, etc.). Entonces no hay impulso = /
Aunque esta publicación tiene años, apareció cuando estaba buscando una respuesta similar, y la respuesta que terminé usando, ni siquiera está en ella. Así que estoy agregando el que encontré;
#include <random> entrada msdn
Este enfoque construirá un generador aleatorio autónomo, y descubrí que es mucho más aleatorio que rand()%x ; más de unos cientos de miles de iteraciones. rand()% nunca arrojaría más de 16 cara / cruz en una fila, cuando debería intentar 65k cada 65k. Este no solo hace eso, sino que lo hace en un cuarto del tiempo.
Así es como implemento #include <random> yo mismo:
//create rng_gen, using mt technique, with range 0,1 (coin) and 1,6(dice);
std::random_device rd; //seed
std::mt19937 gen(rd()); //seed for rd(merzenne twister)
std::uniform_int_distribution<> rng_coin(0, 1); //rng1 range
std::uniform_int_distribution<> rng_dice(1, 6); ///rng2 range
rng_coin(gen); //will apply rng1 range on (gen) object. Is very fast
rng_dice(gen); //will apply rng2 range, returns int.
//will output 1000 cointosses to console
for (int i=0;i<1000;++i)std::cout<<rng_coin(gen)<<"/n";
//will generate 1000 dice throws
for (int i=0;i<1000;++i)rng_dice(gen);
Comenzando con la arquitectura de Ivy Bridge , Intel agregó la instrucción RdRand CPU y AMD la agregó más adelante en junio de 2015. Por lo tanto, si se dirige a un procesador que es lo suficientemente nuevo y no le molesta usar el ensamblado (en línea), la forma más rápida de generar números aleatorios al llamar a la instrucción CPU RdRand para obtener un número aleatorio de 16, 32 o 64 bits como se describe here . Desplácese hasta aproximadamente la mitad de la página para ver ejemplos de código. En ese enlace también hay un ejemplo de código para verificar la CPU actual para el soporte de la instrucción RdRand, y también vea la Wikipedia para una explicación de cómo hacer esto con la instrucción CPUID.
Pregunta relacionada: ¿ Utiliza el verdadero generador de números aleatorios del hardware de sandy bridge? (aunque según Wikipedia, la instrucción RdRand apareció por primera vez en Ivy Bridge, pero no en la arquitectura Sandy Bridge, como dice la pregunta)
Ejemplo de código de C ++ basado en _rdrand64_step() :
#include <immintrin.h>
uint64_t randVal;
if(!_rdrand64_step(&randVal)) {
// Report an error here: random number generation has failed!
}
// If no error occured, randVal contains a random 64-bit number
Creo que WELL es bastante bueno, y WELL512a es bastante corto. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a también es complejo en ese momento. Sin embargo, WELL genera un número entre 0 y 1.
Dos buenas alternativas del sitio de Intel:
1) fastrand: es 2.01 X más rápido que el std rand (). La rutina devuelve un entero, rango de valores de salida similar a C lib.
inline int fastrand() {
g_seed = (214013*g_seed+2531011);
return (g_seed>>16)&0x7FFF;
}
2) una versión SSE (ver el enlace a continuación) es aproximadamente 5.5 X tan rápido como std rand () sin embargo, genera 4 valores aleatorios a la vez, requiere un procesador con sse (casi todos lo hacen), y es más complicado.
El Mersenne Twister tiene algunas implementaciones rápidas.
El otro hilo mencionó el generador xorshf de Marsaglia, pero nadie publicó el código.
static unsigned long x=123456789, y=362436069, z=521288629;
unsigned long xorshf96(void) { //period 2^96-1
unsigned long t;
x ^= x << 16;
x ^= x >> 5;
x ^= x << 1;
t = x;
x = y;
y = z;
z = t ^ x ^ y;
return z;
}
Lo he usado por todos lados. El único lugar donde falló fue cuando estaba tratando de producir matrices binarias aleatorias. Más allá de las matrices de 95x95, comienza a generar muy pocas matrices singulares o demasiadas (se me olvida cuál). Se ha demostrado que este generador es equivalente a un registro de realimentación de desplazamiento lineal. Pero a menos que estés haciendo una criptografía o un trabajo serio de monte carlo, este generador oscila.
La biblioteca Boost tiene un conjunto de generadores aleatorios. La tabla de rendimiento se puede encontrar here .
EDITAR: Esta respuesta fue aquí antes de la edición de la pregunta original. Pero espero que pueda ser útil, así que lo dejo aquí.
Vea estos generadores del generador de números aleatorios George Marsaglia. Están implementados como macros C, y son muy rápidos, solo unas pocas operaciones por número generado.
rand () es muy rápido, y no creo que encuentres mucho más rápido.
Si de hecho lo está frenando (cosa que dudo un poco), entonces necesita un cambio de arquitectura.
Recomiendo completar previamente una larga lista con números aleatorios , y luego cuando la necesite, simplemente tome uno de la lista, en lugar de generar uno. Es posible que pueda volver a llenar la lista con un hilo de fondo.