Tuesday, October 07, 2008

Java has no upper_bound?

I can't find an upper_bound() equivalent in the Java sorted containers.
Looking at TreeMap, we can use the TreeMap.tailMap.firstKey to get the lower_bound.
No function for upper_bound.

I googled on this for a bit and came across some posts that mis-represented what lower_bound, upper_bound means using the standard definition.

This is a useful function and we can code it up with TreeMap.tailmap, but it is useful enough I feel it should be available in the sorted containers in the JDK.

Today I needed an upper_bound() utility for the following task. I keep track of a set of advertisements to be served to the browser. Each advertisement has a weight associated with it based on its past performance. The weights of all advertisements add up to 100.

So for each web request, I need to return an advertisement based on these weights. If I had 2 advertisements with weights 80,20 then I would return the first advertisement 80% of the time.

I implement this with a TreeMap that maps the cumulative weight to the Advertisement. So for the example above it will look like this:

80 -> Ad 1
100 -> Ad 2

Now, all I need to do is to generate a random number greater >= 0 and < 100, and take its upper_bound. That would point me to the advertisement I should return.

Using lower_bound is technically in-correct. Unless I generate the random numbers >=1 and <=100. This can be done, but ideally if Java had an upper_bound() there will be less such work we have to do as programmers.

No comments: