Assume I have a list of items each with a weight and I want to pick a random item. The easiest way to implement this is to keep the list of items and a running sum of the weights sorted by the sum. Then pick a random int from the max weight and do a binary search to find the item matching the random value. Not hard to do.
The question is there a more optimal way to choose the item than a binary search?
In my case I have 50,000 items and the weights are in a similar magnitude (ints) which precludes simply duplicating the items by weight times which makes picking one a simple array reference.
I don't need to know how to do this I simply wonder if there is a faster algorithm? I may want to do a lot of these so speed may be useful but memory isn't unlimited.
I'm using C++ in this case but doesn't have to be in any specific language.
