0

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.

We should assume that the weight/probability of the objects will be a float value between 0 and 1.

First of all, the objects in the list should implement a "Weighted" interface:

public interface Weighted {

     public float getWeight();

}

And then we should extend ArrayList this way:

public class RandomWeightedList<T extends Weighted> extends ArrayList<T>{

    public T extractRandomWeightedObject(){

        //We sum all the weights
        float weightSum = 0F;
        for(int i=0;i<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<this.size();i++){
            upperRangeLimit = lowerRangeLimit + this.get(i).getWeight();
            if(random < upperRangeLimit){
                return this.get(i);
            }
            lowerRangeLimit = upperRangeLimit; 
        }

        throw new RuntimeException("Should never reach here...");
    }
}

Finally we would use it like this:

RandomWeightedList<Banner> bannerList = new RandomWeightedList<Banner>();

//Code to fill the list with weighted objects
//...

Banner randomBanner = bannerList.extractRandomWeightedObject();

How could I improve the random extraction algorithm?

Is extending ArrayList a good solution? Any other one?

thanks in advance

***EDIT

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.

***EDIT2

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?

konpai
  • 101
  • 3
  • 12
  • so the probability of selecting Weighted object X from the list is proportional to its weight? For example, a_weight=.2, b_weight=.5, and c_weight=.8, I'd have a list with 2 a's, 5, b's, and 8 c's? – deanosaur Mar 26 '14 at 15:16
  • Thanks for the feed back @deanosaur. Actually we would have 20 a's, 50 b's and 80 c's as we are multiplying by 100. This way the random extraction uses a two decimal precision weight. That brings to my mind that we could parametrize the precision with a custom constructor for our RandomWeightedList. – konpai Mar 27 '14 at 08:08
  • I added another approach for the weighted random extraction much faster for big lists and lower memory consumption – konpai Mar 27 '14 at 12:06
  • possible duplicate of [Select random k elements from a list whose elements have weights](http://stackoverflow.com/questions/2140787/select-random-k-elements-from-a-list-whose-elements-have-weights) – Joe Mar 27 '14 at 13:03
  • Well, I was looking for a more Java oriented solution than the question you point. I did also want more opinions about extending ArrayList class.. – konpai Mar 27 '14 at 13:40

1 Answers1

0

First, I'd recommend against subclassing ArrayList. Doing so means your class IS an ArrayList, and any operations an ArrayList can do are legal to do on your class. That's really not the case here. You should own an ArrayList rather than claiming to be one.

I'd also suggest adding a constructor to set up the weights one time. You shouldn't be recalculating everything every time you want to do an extractRandomWeightedObject() operation.

Finally, what I'd actually recommend is using an alias table for efficiently generating objects with different probabilities (weights). After the initial setup (O(k) for a distribution with k outcomes), alias tables will crank outcomes out in constant time per invocation and with the correct probabilities. You can download a Java implementation from github. That implementation takes probabilities/proportions rather than weights as the input to the constructor, but you can convert from your weighting scheme to probabilities by dividing each object's weight by the total weight of all objects.

pjs
  • 18,696
  • 4
  • 27
  • 56
  • In my case, I need a List that will be constantly modified, adding and removing items from it. So I did need all the ArrayList operations to be legal for my list. I wanted to add the random extraction support to my list. – konpai Apr 07 '14 at 07:49
  • If the list is going to be constantly modified, I think there's no point in adding a constructor. Every new item in the list will have it's probability/weight and the sum should be recalculated before every extraction. – konpai Apr 07 '14 at 08:09
  • About the extraction algorithm, I'll definetly discard my firs solution and I'll have a look at the alias table approach you point. I'm doubtful about how to include it inside the list's implementation. – konpai Apr 07 '14 at 08:11
  • Finally, I have semantic doubt due to my basic english... Which would be a proper name for a list from where we can extract random objects based on a probability? – konpai Apr 07 '14 at 08:12