generazione rapida di insieme casuale, simulazione Monte Carlo

Question

Ho un insieme di numeri ~ 100, desidero eseguire la simulazione MC su questo set, l'idea di base è che ho RANDOMIZE pienamente l'insieme, fare un po 'di confronto / controlli sui primi ~ 20 valori, memorizzare il risultato e ripetere.

Ora l'algoritmo di confronto / controllo effettivo è estremamente veloce in realtà completa in circa 50 cicli di CPU. Con questo in mente, e al fine di ottimizzare queste simulazioni ho bisogno di generare i set casuali il più velocemente possibile.

Al momento sto utilizzando un algoritmo di Moltiplica con Carry da George Marsaglia, che mi offre un intero casuale in 17 cicli di CPU, abbastanza veloce. Tuttavia, utilizzando l'algoritmo mischiare Fisher-Yates devo generare 100 interi casuali, ~ 1700 cicli di CPU. Questo mette in secondo piano il mio tempo rispetto da un lungo modi.

Quindi la mia domanda è: ci sono altre ben note / tecniche robuste per fare questo tipo di simulazione MC, dove posso evitare il tempo di generazione insieme casuale lungo?

I pensato solo scegliere in modo casuale 20 valori dal set, ma poi avrei dovuto fare controlli di collisione per garantire che 20 voci univoche sono stati scelti.

Aggiornamento:

Grazie per le risposte. Ho un'altra domanda per quanto riguarda un metodo ho appena si avvicinò con dopo il mio post. La domanda è: sarà questo fornirà un robusto veramente (assumendo che il RNG è buona) uscita casuale. Fondamentalmente il mio metodo è di creare una matrice di valori interi stessa lunghezza come il mio array di input, impostare ogni valore zero. Ora comincio a caso la scelta di 20 valori dal set di input in questo modo:

int pcfast[100];
memset(pcfast,0,sizeof(int)*100);
int nchosen = 0;
while (nchosen<20)
{
    int k = rand(100); //[0,100]
    if ( pcfast[k] == 0 )
    {
        pcfast[k] = 1;
        r[nchosen++] = s[k]; // r is the length 20 output, s the input set.
    }
}

Fondamentalmente quello che citato sopra, scegliendo 20 valori a caso, tranne che sembra un modo piuttosto ottimizzato per garantire collisioni. Sarà questo fornire una buona uscita a caso? Il suo abbastanza veloce.

Answer 1

Se si utilizza solo i primi 20 valori nella matrice randomizzato, allora avete solo bisogno di fare 20 passi dell'algoritmo Fisher-Yates (versione di Knuth). Poi 20 valori sono stati randomizzati (sino alla fine della matrice anziché all'inizio, nel solito formulazione), nel senso che i rimanenti 80 passi dell'algoritmo sono garantiti non spostarli. Le altre 80 posizioni non sono completamente mescolate, ma che importa?

codice C ++ (iteratori dovrebbe essere ad accesso casuale):

using std::swap;

template <typename Iterator, typename Rand> // you didn't specify the type
void partial_shuffle(Iterator first, Iterator middle, Iterator last, Rand rnd) {
    size_t n = last - first;
    while (first != middle) {
        size_t k = rnd(n);   // random integer from 0 to n-1
        swap(*(first+k),*first);
        --n;
        ++first;
    }
}

Al ritorno, i valori da first fino alla middle-1 vengono mescolate. Utilizzare in questo modo:

int arr[100];
for (int i = 0; i < 100; ++i) arr[i] = i;
while (need_more_samples()) {
    partial_shuffle(arr, arr+20, arr+100, my_prng);
    process_sample(arr, arr+20);
}

Answer 2

Il libro di simulazione Ross suggerisce qualcosa di simile al seguente:

double return[10];
for(int i=0, n=100; i < 10; i++) {
  int x = rand(n);  //pseudocode - generate an integer on [0,n]
  return[i] = arr[x];
  arr[x] = arr[n];
  n--;
}