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.

1 comment:

Blogger said...

If you need your ex-girlfriend or ex-boyfriend to come crawling back to you on their knees (no matter why you broke up) you got to watch this video
right away...

(VIDEO) Want your ex CRAWLING back to you...?