1 | | 1. Instead of storing the probability of item type K, store the probability of 0 .. K-1 (cumulative). Then roll a number from 0 to total-1 and use binary search. |
| 1 | Instead of iterating over every entry in an alloc table to find an item and keeping a cumulative tally while iterating, store the total in the alloc tables and use a binary search to find it. e.g. instead of |
| 2 | |
| 3 | alloc[0] = { item 1, entries 50 } |
| 4 | alloc[1] = { item 2, entries 100 } |
| 5 | alloc[2] = { item 5, entries 30 } |
| 6 | |
| 7 | have |
| 8 | |
| 9 | alloc[0] = { item 1, entries 0 } |
| 10 | alloc[1] = { item 2, entries 50 } |
| 11 | alloc[2] = { item 5, entries 150 } |