CODEWITHSUNDEEP
javaperformancealgorithmsortedmapconcurrentskiplistmap
Dave Lillethun
Dave Lillethun

Reputation: 3108

Performance of removing multiple items from the head of a SortedMap

I'm working in Java and have a SortedMap, which is implemented as a ConcurrentSkipListMap. I need to remove a number of items from the head of the SortedMap - i.e., all items whose key is less than some threshold. The number of items actually removed may end up being 0, 1, or multiple. It is possible, but rather unlikely, that this will cause all items in the entire SortedMap to be removed (i.e., it's extremely likely at least one item will be larger than the threshold, though it's not guaranteed).

It seems to me that there should be a way to do this rather efficiently since we can take advantage of the assumptions that 1) the items to be removed are consecutive, and 2) the first item to be removed is the head of the SortedMap (and per #1, the rest follow consecutively thereafter). If I build my own skip list this is very easy to do, but I'm lazy and don't want to rebuild all the logic already provided for me in the built-in ConcurrentSkipListMap just to have this one custom operation. So my question is, how can I take advantage of those assumptions for performance while using the ConcurrentSkipListMap?

I've come up with the following methods, but don't know if they're really taking advantage of my assumptions:

SortedMap<Date, Item> mymap = ConcurrentSkipListMap<Date, Item>();
addItemsToMap(mymap);
Date threshold = calculateThreshold();

Method 1: Iterate through, removing items until I reach the threshold.

Iterator<Entry<Date, Item>> itr = mymap.entrySet().iterator();
for (Date key = itr.next().getKey(); key.before(threshold); key = itr.next().getKey())
    itr.remove();

Method 2: Repeatedly remove the first item, until the first item exceeds the threshold.

for (Date key = mymap.firstKey(); key.before(threshold); key = mymap.firstKey())
    mymap.remove(key);

Method 3: Get the set of entries from the head to the threshold, then remove all of them.

Iterator<Entry<Date, Item>> itr2 = mymap.headMap(threshold).entrySet().iterator();
while (itr2.hasNext()) {
    itr2.next();
    itr2.remove();
}

Method 4: More elegant version of #3.

mymap.headMap(threshold).clear();

Upvotes: 3

Views: 877

Answers (1)

JHS
JHS

Reputation: 7871

I would suggest you use the tailMap method provided in the ConcurrentSkipListMap class.

Since this Collection is sorted you might have to pass the key to the method from which you need the the data.

You can have a look at the java docs.

For example - Let us assume my ConcurrentSkipListMap has keys 1,2,4,5 and my threshold is 2. I would pass 2 + 1 = 3 to the tailMap method and I would get back a ConcurrentNavigableMap with 4 and 5 in it.

Upvotes: 0

Related Questions