C++-Funktion zum Auswählen aus einer Liste, in der jedes Element eine bestimmte Wahrscheinlichkeit hat

Question

Ich habe ein Array von Structs und eines der Felder in der Struktur ist ein Float. Ich möchte eine der Strukturen auswählen, bei der die Wahrscheinlichkeit, dass sie ausgewählt wird, relativ zum Wert des Floats ist, d.h.

struct s{
  float probability;
  ...
}

s sArray[50];

Wie kann ich am schnellsten entscheiden, welche S ich wählen soll? Gibt es dafür eine Funktion? Wenn ich die Summe aller Wahrscheinlichkeitsfelder wüsste (Achtung, sie wird nicht 1 sein), könnte ich jedes s durchlaufen und vergleichen probability/total_probability mit einer Zufallszahl, wobei die Zufallszahl für jedes s?

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

Ermitteln Sie RAND_MAX, wie Sie sagen. Erzeugen Sie eine Zufallszahl bis zu RAND_MAX. Iterieren Sie durch das Array, indem Sie die Wahrscheinlichkeiten hochzählen, bis Sie Ihre generierte Zufallszahl erreichen oder überschreiten. (Bei nur 50 Elementen sollte die Leistung kein Problem sein, andernfalls speichern Sie die Summen der Wahrscheinlichkeiten einmal in einem anderen Array und führen dann eine Bisektionssuche in diesem Array nach dem Zufallswert durch).