Improving performance of merging lots of sorted maps into one sorted map - java

Question

I have a method that gets a SortedMap as input, this map holds many SortedMap objects, the output of this method should be one SortedMap containing all elements of the maps held in the input map. the method looks like this:

private SortedMap mergeSamples(SortedMap map){
  SortedMap mergedMap = new TreeMap();
  Iterator sampleIt = map.values().iterator();
  while(sampleIt.hasNext())
  {
    SortedMap currMap = (SortedMap) sampleIt.next();
    mergedMap.putAll(currMap);
  }
  return mergedMap;
}

This is a performance killer, what can I improve here?

Answer 1

I don't see anything wrong with your code; all you can really do is try alternative implementations of SortedMap. First one would be ConcurrentSkipListMap and then look at Commons Collections, Google Collections and GNU Trove. The latter can yield very good results especially if your maps' keys and values are primitive types.

Answer 2

Is it a requirement for the input to be a SortedMap? To me it would seem easier if the input was just a Collection or List. That might speed up creating the input, and might make iteration over all contained maps faster.

Other than that I believe the most likely source of improving the performance of this code is by improving the speed of the compareTo() implementation of the values in the the sorted maps being merged.

Answer 3

Your code is as good as it gets. However, it seems to me that the overall design of the data structure needs some overhaul: You are using SortedMap<?, SortedMap<?, ?>, yet the keys of the parent map are not used.

Do you want to express a tree with nested elements with that and your task is it to flatten the tree? If so, either create a Tree class that supports your approach, or use an intelligent way to merge the keys:

public class NestedKey implements Comparable<NestedKey> {

  private Comparable[] entries;

  public NestedKey(Comparable... entries) {
    assert entries != null;
    this.entries = entries;
  }

  public int compareTo(NestedKey other) {
    for(int i = 0; i < other.entries.length; i++) {
      if (i == entries.length)
        return -1; // other is longer then self <=> self is smaller than other
      int cmp = entries[i].compareTo(other.entries[i]);
      if (cmp != 0)
        return cmp;
    }
    if (entries.length > other.entries.length)
      return 1; // self is longer than others <=> self is larger than other
    else
      return 0;
  }

}

The NestedKey entry used as a key for a SortedMap compares to other NestedKey objects by comparing each of its entries. NestedKeys that are in all elements present, but that have more entries are assumed to be larger. Thus, you have a relationship like this:

• NestedKey(1, 2, 3) < NestedKey(1, 2, 4)
• NestedKey(1, 3, 3) < NestedKey(2, 1, 1)
• NestedKey(1, 2, 3) < NestedKey(2)

If you use only one SortedMap that uses NestedKey as its keys, then its .values() set automatically returns all entries, flattened out. However, if you want to use only parts of the SortedMap, then you must use .subMap. For example, if you want all entries wite NestedKeys between 2 and 3 , use .subMap(new NestedKey(2), new NestedKey(3))