title: Randomly selecting an element from a weighted list
body: <p>I have a list of 100,000 objects. Every list element has a "weight" associated with it that is a positive int from 1 to N.</p>
  
  <p>What is the most efficient way to select a random element from the list? I want the behavior that my distribution of randomly chosen elements is the same as the distribution of weights in the list.</p>
  
  <p>For example, if I have a list L = {1,1,2,5}, I want the 4th element to be selected 5/9ths of the time, on average.</p>
  
  <p>Assume inserts and deletes are common on this list, so any approach using "integral area tables" would need to be updated often - hoping there is a solution with O(1) runtime and O(1) extra memory required.</p>