Ho bisogno di un generatore casuale veloce per C++

Question

Sto provando a fare alcuni swap opt-3 sul mio generatore TSP per distanze euclidee, e poiché in molti casi ho più di ~ 500 nodi, devo selezionare casualmente almeno 1 dei 3 nodi che voglio provare a scambiare.

Quindi in pratica ho bisogno di una funzione a numero casuale che sia veloce. (il normale rand() è troppo lento) Non deve essere fantastico, basta sufficiente.

MODIFICA: Ho dimenticato di menzionare, sono seduto in un ambiente in cui non posso aggiungere alcuna libreria ad eccezione della libreria di lingue standard (come STL, iostream ecc.). Quindi nessuna spinta =/

Answer 1

L'altro thread menzionava il generatore di xorshf di Marsaglia, ma nessuno ha pubblicato il codice.

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; 
} 

Ho usato questo dappertutto. L'unico posto che ha fallito è stato quando stavo cercando di produrre matrici binarie casuali. Dopo circa 95x95 matrici, inizia a generare troppe o troppe matrici singolari (non ricordo quale). È stato dimostrato che questo generatore è equivalente a un registro di feedback di spostamento lineare. Ma a meno che tu non stia facendo della crittografia o del serio lavoro di monte carlo, questo generatore si rompe.

Answer 2

puoi pregenerare un mucchio di bit casuali prima del tempo e staccarli 2 alla volta (dato che hai solo bisogno di un numero casuale compreso tra 1 e 3)?

Answer 3

La libreria Boost dispone di un set di generatori casuali. La tabella delle prestazioni potrebbe essere trovata here.

MODIFICA: questa risposta era qui prima della modifica della domanda originale. Ma spero che potrebbe essere ancora utile, quindi lo lascio qui.

Answer 4

Il Mersenne Twister ha alcune implementazioni veloci.

Answer 5

rand() è davvero dannatamente veloce e non credo che lo troverete molto più veloce.

Se in effetti si sta rallentando (cosa di cui dubito), allora è necessario un cambiamento di architettura.

Si consiglia di precompilare una lunga lista con numeri casuali, quindi quando ne occorre uno, basta prenderne uno dall'elenco, anziché generarne uno. Potresti essere in grado di riempire nuovamente l'elenco con un thread in background.

Answer 6

Vedere these generators dall'esperto di generatore di numeri casuali George Marsaglia. Sono implementati come macro C, e sono fulminei, solo poche operazioni per numero generato.

Answer 7

Due buone alternative dal sito di Intel:

1) fastrand - è 2,01 volte più veloce rispetto al rand std(). La routine restituisce un intero, intervallo di valori di uscita simile a C lib.

inline int fastrand() { 
    g_seed = (214013*g_seed+2531011); 
    return (g_seed>>16)&0x7FFF; 
} 

2) una versione SSE (vedi link sotto) è di circa 5,5 X più velocemente std rand(), tuttavia genera 4 valori casuali alla volta, richiede un processer con SSE (quasi tutti lo fanno), e è più complicato.

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

Answer 8

ci penso bene è piuttosto buona, e WELL512a è piuttosto breve. http://www.iro.umontreal.ca/~panneton/WELLRNG.html WELL44497a è complesso al momento anche. Tuttavia, WELL genera un numero compreso tra 0 e 1.

Answer 9

Anche se questo post è vecchio di anni, si è presentato quando stavo cercando una risposta simile, e la risposta che ho terminato usando, non è nemmeno in esso. Quindi aggiungo quello che ho trovato;

#include <random> msdn entry

Questo approccio sarà costruire un autonomo generatore casuale, e ho trovato ad essere molto più casuale di rand()%x; in poche centinaia di migliaia di iterazioni. rand()% non getterebbe mai più di 16 teste/croce di fila, quando dovrebbe eseguire altri 65k tentativi. Questo non solo lo fa, ma lo fa in un quarto del tempo.

Questo è il modo a implementare #include <random> me stesso:

//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

Partendo Ivy Bridge architettura Intel ha aggiunto RdRand istruzioni della CPU e AMD ha aggiunto in un secondo momento, nel giugno 2015. Quindi, se si prendono di mira un processore che è nuovo abbastanza e don Non ci si preoccupa di utilizzare l'assembly (inline), il modo più veloce per generare numeri casuali dovrebbe essere nel chiamare l'istruzione della CPU RdRand per ottenere un numero casuale a 16 o 32 o 64 bit come descritto here. Scorri fino a circa la metà della pagina per gli esempi di codice. A quel link c'è anche un esempio di codice per controllare la CPU corrente per il supporto dell'istruzione RdRand, e vedere anche Wikipedia per una spiegazione su come farlo con l'istruzione CPUID.

questione connessa: Making use of sandy bridge's hardware true random number generator? (anche se secondo Wikipedia, RdRand istruzioni prima apparizione nel Ivy Bridge, ma non architettura Sandy Bridge, come quella domanda dice)

codice

Esempio C++ basata su _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