CODEWITHSUNDEEP
javahadooptreemap
Simoyw
Simoyw

Reputation: 691

How to sum two TreeMap in Java efficiently?

I have multiple TreeMap that I want to sum in only one TreeMap summing value of the same key and efficently. Like:

   TreeMap<String,Long> sum(TreeMap<String,Long> tm1,TreeMap<String,Long> tm2);

I tried to make this, but 1. I can not convert the list resulting into a TreeMap again and 2. key are duplicated if equals:

    TreeMap<String,Long> tm1=new TreeMap<String, Long>();
    ...
    TreeMap<String,Long> tm2=new TreeMap<String, Long>();
    ...       
    List<Map.Entry<String,Long>> first = new ArrayList<Map.Entry<String,Long>>(tm1.entrySet());
    List<Map.Entry<String,Long>> second = new ArrayList<Map.Entry<String,Long>>(tm2.entrySet());
    Iterable<Map.Entry<String,Long>> all = Iterables.mergeSorted(
            ImmutableList.of(first, second), new Ordering<Map.Entry<String, Long>>() {
        @Override
        public int compare(java.util.Map.Entry<String, Long> stringLongEntry, java.util.Map.Entry<String, Long> stringLongEntry2) {
            return stringLongEntry.getKey().compareTo(stringLongEntry2.getKey());
        }
    });
    TreeMap<String,Long> mappedMovies = Maps.uniqueIndex(... ??)

Edit: I can't use Java 8 because this program run in a Hadoop program in Amazon Web Services that support only Java 1.7.

Upvotes: 0

Views: 2456

Answers (2)

wassgren
wassgren

Reputation: 19231

You can use Java 8 Streams to achieve this. Consider the following code:

// Testdata - The first map
Map<String, Long> m1 = new TreeMap<>();
m1.put("A", 1L);
m1.put("B", 1L);
m1.put("C", 1L);

// Testdata - The second map
Map<String, Long> m2 = new TreeMap<>();
m2.put("C", 2L);
m2.put("D", 2L);
m2.put("E", 2L);

// Summarize using streams
final Map<String, Long> summarized =
        Stream.concat(m1.entrySet().stream(), m2.entrySet().stream())     // Stream both maps
              .collect(Collectors.groupingBy(                             // Collect the map
                          Map.Entry::getKey,                              // Group by key
                          Collectors.summingLong(Map.Entry::getValue)));  // Value is the sum

System.out.println("Summarized: " + summarized);                          // Print the output

The summarized Map is grouped on the key and summarized on the value. The output is:

Summarized: {A=1, B=1, C=3, D=2, E=2}


If you want to put this in a function, simply do it like this:

public Map<String, Long> summarize(
        final Map<String, Long> m1, 
        final Map<String, Long> m2) {

    return Stream.concat(m1.entrySet().stream(), m2.entrySet().stream())
                 .collect(groupingBy(
                          Map.Entry::getKey,
                          summingLong(Map.Entry::getValue)));
}

To read more about Java 8 streams, check out the Oracle docs.

Upvotes: 3

Niels Billen
Niels Billen

Reputation: 2199

The following function calculates the sum:

public static TreeMap<String, Long> sum(TreeMap<String, Long> first,
        TreeMap<String, Long> second) {
    TreeMap<String, Long> result = new TreeMap<String, Long>(first);

    for (Entry<String, Long> e : second.entrySet()) {
        Long l = result.get(e.getKey());
        result.put(e.getKey(), e.getValue() + (l == null ? 0 : l));
    }

    return result;
}

Test code:

TreeMap<String, Long> first = new TreeMap<String, Long>();
TreeMap<String, Long> second = new TreeMap<String, Long>();

first.put("x", 1L);
first.put("y", 5L);

second.put("x", 2L);
second.put("y", 3L);
second.put("z", 5L);

System.out.println(sum(first, second));

Output:

{x=3, y=8, z=5}

Edit

A small optimization would be to copy the largest TreeMap and iterate over the smallest. This reduces the number of lookups/insertions.

public static TreeMap<String, Long> sum(TreeMap<String, Long> first,
        TreeMap<String, Long> second) {
    // optimization (copy the largest tree map and iterate over the
    // smallest)
    if (first.size() < second.size()) {
        TreeMap<String, Long> t = first;
        first = second;
        second = t;
    }

    TreeMap<String, Long> result = new TreeMap<String, Long>(first);

    for (Entry<String, Long> e : second.entrySet()) {
        Long l = result.get(e.getKey());
        result.put(e.getKey(), e.getValue() + (l == null ? 0 : l));
    }

    return result;
}

Upvotes: 1

Related Questions