Is there a faster way to make random weighted choices for a large list of items

Question

Suppose I have a list of items, each with a weight, and I want to select a random item. The easiest way to implement this is to keep a list of items and the current sum of weights sorted by sum. Then select a random int from the maximum weight and do a binary search to find the element matching the random value. Not difficult.

Question: Is there a better way to select an item than binary search?

In my case, I have 50,000 items, and the scales have a similar value (ints), which eliminates just duplication of elements by weight times, which makes the choice of one simple reference to the array.

I do not need to know how to do this. I'm just wondering if there is a faster algorithm? I might want to do a lot of them, so speed can be useful, but memory is not unlimited.

I use C ++ in this case, but do not have to be in any particular language.