Funzione C++ per il prelievo da una lista in cui ogni elemento ha una probabilità distinta

Question

Ho una matrice di strutture e uno dei campi nella struct è un float. Voglio scegliere una delle strutture in cui la probabilità di selezionarlo è relativa al valore del float. ie

struct s{ 
    float probability; 
    ... 
} 

s sArray[50]; 

Qual è il modo più veloce per decidere quale scegliere? C'è una funzione per questo? Se conoscessi la somma di tutti i campi di probabilità (Nota che non sarà 1), allora potrei scorrere ogni s e confrontare probability/total_probability con un numero casuale, cambiando il numero casuale per ogni s? ie

if((float) (rand()/RAND_MAX) < probability)... 

Answer 1

float p = (rand()/static_cast<float>(RAND_MAX)) * total_probability; 
s* current = &sArray[0]; 
while ((p -= current->probability) > 0) 
    ++current; 
// `current` now points to your chosen target 

Answer 2

Trova RAND_MAX come dici tu. Genera un numero casuale fino a RAND_MAX. Iterate attraverso l'array contando le probabilità finché non siete uguali o superiori al numero casuale generato. (con solo 50 prestazioni elemento non dovrebbe essere un problema, altrimenti memorizzare le somme delle probabilità una volta in un altro array e poi fare una ricerca di bisezione in quella per il valore casuale.)