Generazione di m numeri casuali distinti nell’intervallo

Ho due metodi per generare m numeri casuali distinti nell’intervallo [0..n-1]

Metodo 1:

//C++-ish pseudocode int result[m]; for(i = 0; i < m; ++i) { int r; do { r = rand()%n; }while(r is found in result array at indices from 0 to i) result[i] = r; } 

Metodo 2:

 //C++-ish pseudocode int arr[n]; for(int i = 0; i < n; ++i) arr[i] = i; random_shuffle(arr, arr+n); result = first m elements in arr; 

Il primo metodo è più efficiente quando n è molto più grande di m, mentre il secondo è più efficiente altrimenti. Ma “molto più grande” non è una nozione così rigida, vero? 🙂

Domanda: Quale formula di n e m dovrei usare per determinare se method1 o method2 saranno più efficienti? (in termini di aspettativa matematica del tempo di esecuzione)

Pura matematica:
Calcoliamo la quantità di chiamate di funzione rand() in entrambi i casi e confrontiamo i risultati:

Caso 1: vediamo le aspettative matematiche delle chiamate sul passaggio i = k , quando si hanno già k numeri scelti. La probabilità di ottenere un numero con una chiamata a rand() è uguale a p = (nk)/n . Abbiamo bisogno di conoscere l’aspettativa matematica di tale quantità di chiamate che porta ad ottenere un numero che non abbiamo ancora.

La probabilità di farlo usando 1 chiamata è p . Usando 2 chiamate – q * p , dove q = 1 - p . In generale, la probabilità di ottenerla esattamente dopo n chiamate è (q^(n-1))*p . Quindi, l’aspettativa matematica è
Sum[ n * q^(n-1) * p ], n = 1 --> INF . Questa sum è uguale a 1/p (dimostrato da wolfram alpha).

Quindi, sul passo i = k eseguirai 1/p = n/(nk) chiamate della funzione rand() .

Ora riassumiamolo nel complesso:

Sum[ n/(n - k) ], k = 0 --> m - 1 = n * T – il numero di chiamate rand nel metodo 1.
Qui T = Sum[ 1/(n - k) ], k = 0 --> m - 1

Caso 2:

Qui rand() è chiamato all’interno random_shuffle n - 1 volte (nella maggior parte delle implementazioni).

Ora, per scegliere il metodo, dobbiamo confrontare questi due valori: n * T ? n - 1 n * T ? n - 1 .
Quindi, per scegliere il metodo appropriato, calcolare T come descritto sopra. Se T < (n - 1)/n è meglio usare il primo metodo. Usa il secondo metodo altrimenti.

Controlla la descrizione di Wikipedia dell’algoritmo Fisher-Yates originale . Si consiglia di utilizzare essenzialmente il metodo 1 per un massimo di n / 2 e il metodo 2 per il resto.

Personalmente, userei il Metodo 1, e quindi se M> N / 2, scelgo i valori NM, e quindi invero l’array (restituisco i numeri che non sono stati prelevati). Ad esempio, se N è 1000 e ne vuoi 950, scegli 50 valori utilizzando il Metodo 1, quindi restituisci l’altro 950.

Modifica: Tuttavia, se il tuo objective è il rendimento costante, utilizzerei un metodo modificato 2, che non esegue il shuffle completo, ma mischia solo i primi elementi M della tua matrice di lunghezza N.

 int arr[n]; for(int i = 0; i < n; ++i) arr[i] = i; for (int i =0; i < m; ++i) { int j = rand(ni); // Pick random number from 0 <= r < ni. Pick favorite method // j == 0 means don't swap, otherwise swap with the element j away if (j != 0) { std::swap(arr[i], arr[i+j]); } } result = first m elements in arr; 

Ecco un algoritmo che funzionerà nella memoria O (n) e nel tempo O (n) (dove n è il numero di risultati restituiti, non la dimensione del set da cui si sta selezionando) per qualsiasi set di risultati. È in Python per comodità perché usa una tabella hash:

 def random_elements(num_elements, set_size): state = {} for i in range(num_elements): # Swap state[i] with a random element swap_with = random.randint(i, set_size - 1) state[i], state[swap_with] = state.get(swap_with, swap_with), state.get(i, i) return [state[i] for i in range(num_elements) # effectively state[:num_elements] if it were a list/array. 

Questo è solo un parziale shuffle da pesca, con l’array che viene mischiato implementato come un hashtable sparse – ogni elemento che non è presente è uguale al suo indice. num_elements i primi indici num_elements e restituiamo quei valori. Nel caso in cui set_size = 1, questo è equivalente al prelievo di un numero casuale nell’intervallo e nel caso in cui num_elements = set_size , questo è equivalente a un normale shuffle fisher-yates.

È banale osservare che questo è il tempo O (n), e poiché ogni iterazione del ciclo inizializza al massimo due nuovi indici nella tabella hash, è anche lo spazio O (n).

Che ne dici di un terzo metodo?

 int result[m]; for(i = 0; i < m; ++i) { int r; r = rand()%(ni); r += (number of items in result <= r) result[i] = r; } 

Modifica dovrebbe essere < =. e sarebbe in realtà una logica aggiuntiva per evitare le collisioni.

Questo è meglio, un esempio che usa il metodo moderno di Fisher-Yates

 //C++-ish pseudocode int arr[n]; for(int i = 0; i < n; ++i) arr[i] = i; for(i = 0; i < m; ++i) swap(arr, ni, rand()%(ni) ); result = last m elements in arr; 

Parlando di aspettativa matematica, è abbastanza inutile ma lo posterò comunque: D

Shuffle è semplice O (m).

Ora l’altro algoritmo è un po ‘più complesso. Il numero di passaggi necessari per generare il numero successivo è il valore atteso del numero di prove e la probabilità della lunghezza di prova è una distribuzione geometrica. Così…

 p=1 E[X1]=1 = 1 = 1 p=1-1/n E[x2]=1/(1-1/n) = 1 + 1/(n-1) = 1 + 1/(n-1) p=1-2/n E[x3]=1/(1-1/n) = 1 + 2/(n-2) = 1 + 1/(n-2) + 1/(n-2) p=1-3/n E[X4]=1/(1-2/n) = 1 + 3/(n-3) = 1 + 1/(n-3) + 1/(n-3) + 1(n-3) .... p=1-(m-1)/n) E[Xm]=1/(1-(m-1)/n)) 

Si noti che la sum può essere divisa in una forma triangular, vedere a destra.

Usiamo la formula per le serie armoniche: H_n = Sum k = 0-> n (1 / k) = approx ln (k)

 Sum(E[Xk]) = m + ln(n-1)-ln(nm-1) + ln(n-2)-ln(nm-1) + ... = m + ln(n-1) + ln(n-2) + ... - (m-1)*ln(nm-1) .. 

E c’è qualche forum per la sum delle serie armoniche, se sei ancora interessato cercherò …

Aggiornamento : in realtà è una formula molto carina (grazie al brillante libro di Concrete Mathematics)

 Sum(H_k) k=0->n = n*H_n - n 

Quindi il numero previsto di passaggi:

 Sum(E[Xk]) = m + (n-1)*ln(n-1) - (n-1) - (nm-1)*ln(nm-1) - (nm-1)) - (m-1)*ln(nm-1). 

Nota: non l’ho verificato

Questo è un po ‘lungo, ma potrebbe funzionare, a seconda del sistema.

  1. Inizia con un ragionevole rapporto, come 0,5.
  2. Quando arriva una richiesta, elaborala con qualsiasi metodo ottieni dal valore corrente del rapporto di soglia.
  3. Registra il tempo necessario e quando hai tempo “vuoto”, esegui la stessa operazione con l’altro metodo.
  4. Se la soluzione alternativa è molto più veloce di quella originale, regola la soglia in alto o in basso.

Il difetto evidente in questo metodo è che su sistemi di carico altamente variabili il tuo test “offline” non sarà troppo affidabile.

Ci fu suggerito il rimescolamento di Fisher-Yates. Non so se il prossimo codice genera interi distribuiti equamente, ma è almeno compatto e one-pass:

 std::random_device rd; std::mt19937 g(rd()); for (size_type i = 1; i < std::size(v); ++i) { v[i] = std::exchange(v[g() % i], i); } 

Molto probabilmente sarebbe più semplice avviarlo in modalità debug (e mantenere un metodo come nota) per un paio di volte per ottenere una media, quindi usare l’altro metodo per ottenere una media da quella

Non consiglio questo metodo ma funziona

 #include  #include  #include  using namespace std; int randArray[26]; int index = 0; bool unique(int rand) { for (int i = 0; i < index; i++) if (rand == randArray[i]) return false; index++; return true; } int main() { srand(time(NULL)); for (int i = 1; i < 26; i++) randArray[i] = -1; for (int i = 0; i < 26; i++) { randArray[i] = rand() % 26; while (!unique(randArray[i])) { randArray[i] = rand() % 26; } } for (int i = 0; i < 26; i++) { cout << randArray[i] << " "; } cout << "\n" << index << endl; return 0; }