Algorithm

Weighted Random: algorithms for sampling from discrete probability distributions

The optimal solution for weighted random should be the Alias Method. It requires $O(n)$ time to initialize, $O(1)$ time to make a selection, and $O(n)$ memory.