Necesito un generador aleatorio rápido para C++

Question

Estoy tratando de hacer un intercambio de opt-3 en mi generador TSP para distancias euclidianas, y dado que en muchos casos tengo más de ~ 500 nodos, necesito seleccionar aleatoriamente al menos 1 de los 3 nodos que quiero probar intercambiando.

Así que básicamente necesita una función de números aleatorios que es rápida. (el rand normal() es demasiado lento) No tiene que ser increíble, solo bueno suficiente.

EDIT: Olvidé mencionar que estoy sentado en un entorno en el que no puedo agregar ninguna biblioteca, excepto la biblioteca de idiomas estándar (como STL, iostream, etc.). Así que no hay impulso =/

Answer 1

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 todas partes. 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.

Answer 2

puede que pregenerate un montón de bits aleatorios antes de tiempo y pelarlos 2 a la vez (ya que sólo necesita un número aleatorio entre 1 y 3)?

Answer 3

Boost library 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í.

Answer 4

El Mersenne Twister tiene algunas implementaciones rápidas.

Answer 5

rand() es muy rápido, y no creo que puedas encontrar mucho más rápido.

Si de hecho está frenando (lo que dudo un poco), entonces necesita un cambio de arquitectura.

Recomiendo llenar previamente una lista larga con los números aleatorios, luego, cuando lo 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.

Answer 6

Consulte these generators 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.

Answer 7

Dos buenas alternativas desde el sitio de Intel:

1) fastrand - es 2,01 veces más rápido que el rand std(). 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 enlace más abajo) es de aproximadamente 5,5 X tan rápido como rand std() sin embargo, genera 4 valores aleatorios a la vez, requiere una procesadora con sse (casi todos lo hacen), y es mas complicado

http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/

Answer 8

que pensar bien es bastante bueno, y WELL512a es bastante corto. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a es complejo en ese momento también. Sin embargo, WELL genera un número entre 0 y 1.

Answer 9

Aunque esta publicación tiene muchos 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> msdn entry

Este enfoque va a construir un autónomo generador aleatorio, y me pareció que para ser mucho más al azar 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> 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); 

Answer 10

A partir de Ivy Bridge arquitectura Intel añadió RdRand instrucciones de la CPU y AMD añadió más tarde, en junio de 2015. Así que si usted está apuntando a un procesador que es lo suficientemente nueva y don No importa ensamblar (en línea), la forma más rápida de generar números aleatorios debe ser llamar a la instrucción RdRand de la CPU para obtener un número aleatorio de 16, 32 o 64 bits como se describe en 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: Making use of sandy bridge's hardware true random number generator? (aunque según la Wikipedia, RdRand instrucción apareció por primera vez en Ivy Bridge, pero no la arquitectura Sandy Bridge que dicha cuestión se dice)

código

Ejemplo C++ basa 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