C ++ функция для выбора из списка, где каждый элемент имеет определенную вероятность

Question

У меня есть массив структур, и одно из полей в структуре является плавающей точкой. Я хочу выбрать одну из структур, где вероятность ее выбора относительно стоимости поплавка. т.е.

struct s{
  float probability;
  ...
}

s sArray[50];

Какой самый быстрый способ решить, какой выбрать? Есть ли функция для этого? Если бы я знал сумму всех полей вероятности (обратите внимание, что это не будет 1), то мог бы я перебрать все s и сравнить probability/total_probability со случайным числом, меняя случайное число для каждого 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

Узнайте RAND_MAX, как вы говорите. Генерация случайного числа до RAND_MAX. Итерируйте по массиву, считая вероятности, пока вы не сравняете или не сгенерируете случайное число. (При производительности всего 50 элементов проблем не должно быть, в противном случае сохраните суммы вероятностей один раз в другом массиве, а затем выполните поиск пополам по случайному значению.)