algorithm - Data structure for loaded dice? -

suppose have n-sided loaded die each side k has probability p_k of coming when roll it. i'm curious if there algorithm storing information statically (i.e. fixed set of probabilities) can efficiently simulate random roll of die.

currently, have o(lg n) solution problem. idea store table of cumulative probability of first k sides k, them generate random real number in range [0, 1) , perform binary search on table largest index cumulative value no greater chosen value. rather solution, seems odd runtime doesn't take probabilities account. in particular, in extremal cases of 1 side coming or values being uniformly distributed, it's possible generate result of roll in o(1) using naive approach, though solution still take logarithmicallh many steps.

does have suggestions how solve problem in way somehow "adaptive" in it's runtime?

edit: based on answers question, have written an article describing many approaches problem, along analyses. looks vose's implementation of alias method gives θ(n) preprocessing time , o(1) time per die roll, impressive. useful addition information contained in answers!

you looking alias method provides o(1) method generating fixed discrete probability distribution (assuming can access entries in array of length n in constant time) one-time o(n) set-up. can find documented in chapter 3 (pdf) of "non-uniform random variate generation" luc devroye.

the idea take array of probabilities p_k , produce 3 new n-element arrays, q_k, a_k, , b_k. each q_k probability between 0 , 1, , each a_k , b_k integer between 1 , n.

we generate random numbers between 1 , n generating 2 random numbers, r , s, between 0 , 1. let = floor(r*n)+1. if q_i < s return a_i else return b_i. work in alias method in figuring out how produce q_k, a_k , b_k.