title: Retrieve random object from list based on probability
body: <p>I have to retrieve a random object from a list based on the weights/probabilities of the objects. I've found different solutions to the problem, but I'd like to share another approach to know if it's a good one or how could it be improved.</p>
  
  <p>We should assume that the weight/probability of the objects will be a float value between 0 and 1.</p>
  
  <p>First of all, the objects in the list should implement a "Weighted" interface:</p>
  
  <pre><code>public interface Weighted {
  
       public float getWeight();
  
  }
  </code></pre>
  
  <p>And then we should extend ArrayList this way:</p>
  
  <pre><code>public class RandomWeightedList&lt;T extends Weighted&gt; extends ArrayList&lt;T&gt;{
  
      public T extractRandomWeightedObject(){
  
          //We sum all the weights
          float weightSum = 0F;
          for(int i=0;i&lt;this.size();i++){
              weightSum += this.get(i).getWeight();
          }
  
          //We generate a random float between 0 and weight sum
          float random = (new Random()).nextFloat() * weightSum;
  
          //We start range limits
          float lowerRangeLimit = 0;
          float upperRangeLimit = 0;
  
          //We iterate the list calculating the upper range limit and we check
          // wether the random number is lower than the upper limit. If it is, 
          // we save the instance and break;
          for(int i=0;i&lt;this.size();i++){
              upperRangeLimit = lowerRangeLimit + this.get(i).getWeight();
              if(random &lt; upperRangeLimit){
                  return this.get(i);
              }
              lowerRangeLimit = upperRangeLimit; 
          }
  
          throw new RuntimeException("Should never reach here...");
      }
  }
  </code></pre>
  
  <p>Finally we would use it like this:</p>
  
  <pre><code>RandomWeightedList&lt;Banner&gt; bannerList = new RandomWeightedList&lt;Banner&gt;();
  
  //Code to fill the list with weighted objects
  //...
  
  Banner randomBanner = bannerList.extractRandomWeightedObject();
  </code></pre>
  
  <p>How could I improve the random extraction algorithm? </p>
  
  <p>Is extending ArrayList a good solution? Any other one?</p>
  
  <p>thanks in advance</p>
  
  <h2>***EDIT</h2>
  
  <p>I changed the random object extraction algorithm by a solution with lower memory consumption and higher performance for big lists. And there's no need to parametrize precision in this case.</p>
  
  <h2>***EDIT2</h2>
  
  <p>I have a semantic doubt about the naming of the List and the interface. Any suggestion for naming an interface that refers to a object with a probability field? and for a List from where a random object can be extracted based on it's probability?</p>