9

I have an array of structs and one of the fields in the struct is a float. I want to pick one of the structs where the probability of picking it is relative to the value of the float. ie

struct s{
  float probability;
  ...
}

s sArray[50];

What is the fastest way to decide which s to pick? Is there a function for this? If I knew the sum of all the probability fields (Note it will not be 1), then could I iterate through each s and compare probability/total_probability with a random number, changing the random number for each s? ie

if( (float) (rand() / RAND_MAX) < probability)...
Stuart
  • 1,733
  • 4
  • 21
  • 34

2 Answers2

11
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
rlbond
  • 65,341
  • 56
  • 178
  • 228
  • `rand() / static_cast(RAND_MAX)` will always be either 0 (with very high probability) or 1 (with very low probability). You could try `rand() / static_cast(RAND_MAX)` instead. – Matthew T. Staebler Apr 16 '10 at 00:35
  • @Stuart and @Aeth: you're both correct with your changes. I was using `double` for my test code but wanted to change it to float to match the question. Somehow I put `long` instead :( – rlbond Apr 16 '10 at 01:34
  • You should also check to make sure `current` does not point past the end of `sArray`. – rlbond Dec 01 '15 at 20:12
3

Find out RAND_MAX as you say. Generate a random number up to RAND_MAX. Iterate through the array counting up the probabilities until you equal or exceed your generated random number. (With only 50 element performance shouldn't be an issue, otherwise store the sums of the probabilities once in another array and then do a bisection search into that for the random value.)

Trevor Tippins
  • 2,827
  • 14
  • 10
  • Exact optimization depends on how often the array is modified compared to how often you pick a random element, and premature optimization is a bad plan anyway. That said, you could keep RAND_MAX up to date while constructing and modifying the array so you don't have to recalculate it every time you pick a random element. You can also store cumulative probabilities so that instead of iterating through and adding individual probabilities, you can just do a binary search on the cumulative probability. – Cascabel Apr 15 '10 at 23:51
  • @Jefromi - I just added that bit to the answer! You were really FAST with that comment!! – Trevor Tippins Apr 15 '10 at 23:53
  • Probabilities will be changing often. Two objects are picked at random and then one or two objects in the array may change. This happens many times. – Stuart Apr 15 '10 at 23:58