CODEWITHSUNDEEP
javaalgorithmlistsearchdictionary
Benjamin M
Benjamin M

Reputation: 24527

Find next smallest key (performance advice needed)

I need some advice in terms of performance. I've got a Map<DateTime, String>. And I need something like the following method:

Map<DateTime, BigDecimal> map; // about 50 entries. Btw: Which impl to choose?

BigDecimal findNextSmaller(DateTime input) {

    DateTime tmp = null;

    for(DateTime d : map.keySet()) {
        if(tmp == null && d < input) {
            tmp = d;
        }
        if(d < input && d > tmp) {
            tmp = d;
        }
    }

    return map.get(tmp);
}

So basically I just iterate over the keySet of my Map and try to find the key which is the next smallest compared to input.

This method will get called about 1.000.000 times in a row:

BigDecimal sum;

List<Item> items; // about 1.000.000 Items

for(Item i : items) {
    sum = sum.add(findNextSmaller(i.getDateTime()));
}

Now I'm looking for a way to make things faster.

My first thought was to make an OrderedList out of the Map's keySet. So in average I just have to iterate over half of the DateTimes. And then just do a map.get(dateTimeFromOrderedList) to get the matching value.

But is that all I can do about it?

Upvotes: 0

Views: 85

Answers (2)

Pyranja
Pyranja

Reputation: 3589

Have a look at NavigableMap. This seems to be exactly what you need.

As you are searching for the DateTime closest and strictly less than the input, I would choose floorEntry(key) for the lookup. But make sure that you are handling nulls correctly. There may not be a key in the map that is strictly smaller than the input! If you try to add a null reference to a BigDecimal, a NullPointerException will be thrown.

Upvotes: 3

assylias
assylias

Reputation: 328608

You can use a TreeMap which has a built-in method for that:

TreeMap<DateTime, BigDecimal> map = new TreeMap<>();
//populate the map

BigDecimal findNextSmaller(DateTime input) {
    return map.ceilingEntry(input).getValue(); //add exception checking as required
}

Note: you may want ceilingEntry or higherEntry depending on whether you want (resp.) >= or >.

Upvotes: 4

Related Questions