Average of multiple vectors with different length

Question

I have several profiles that are in form of mappings (id,value) and I need to find average between that profiles (values). The issue is that not all profile consist of the same ids, so that the lengths are different, as here:

1 2 3 4 5 6
-----------
1 3 - 5 - 9
0 - 1 1 2 -

The first row denotes element_id and rows 2 and 3 denote the user profiles. '-' is the element with no value. The average for these 2 profiles is: {0.5, 3, 1, 3, 2, 9}.

I have implemented is as following:

private static void calcAverage(Map<Integer, Map<Integer, Integer>> profiles) {
        Map<Integer, Float> res = new HashMap<>();
        Map<Integer, Integer> elemcount = new HashMap<>();
        Map<Integer, Integer> elemsums = new HashMap<>();

        for (Map<Integer, Integer> profile : profiles.values()) {
            for (Map.Entry<Integer, Integer> element : profile.entrySet()) {
                if (!elemcount.containsKey(element.getKey())) {
                    elemcount.put(element.getKey(), 1);
                    elemsums.put(element.getKey(), element.getValue());
                } else {
                    int count = elemcount.get(element.getKey());
                    elemcount.put(element.getKey(), count + 1);

                    int sum = elemsums.get(element.getKey());
                    elemsums.put(element.getKey(), element.getValue() + sum);
                }
            }
        }

        for (Map.Entry<Integer, Integer> entry : elemcount.entrySet()) {
            System.out.println(entry.getKey() + " => " + (double)elemsums.get(entry.getKey())/(double)entry.getValue());
        }
    }

The source is working perfectly. It does what I want.

The only thing, I wanted to ask, if it is possible to optimize it somehow? Because when I have 1k profiles with 1k elements each, it will take really much time to work on.

Answer 1

In general, it will be O(N+M) with N>=M where N is number of all values you are going to compute -all values from all profiles- and M is number of unique ids that were present in all profiles and . No other way around it.

public static void main(String[] args) {
    Map<Integer, Integer> p1 = new HashMap<>();
    p1.put(1, 1);
    p1.put(2, 3);
    p1.put(4, 5);
    p1.put(6, 9);

    Map<Integer, Integer> p2 = new HashMap<>();
    p2.put(1, 0);
    p2.put(3, 1);
    p2.put(4, 1);
    p2.put(5, 2);

    Map<Integer, Double> avg = calcAvg(p2,p1);

    System.out.println(avg);
}

private static Map<Integer, Double> calcAvg(Map<Integer, Integer>... profiles) {
    Map<Integer, Integer> counts = new HashMap<>();
    Map<Integer, Integer> sums = new HashMap<>();

    //Here is our N part
    for (Map<Integer, Integer> profile : profiles) {
        for (Entry<Integer, Integer> entry : profile.entrySet()) {
            sums.compute(entry.getKey(), (k, v) -> {
                return v == null ? entry.getValue() : v + entry.getValue();
            });
            counts.compute(entry.getKey(), (k, v) -> {
                return v == null ? 1 : ++v;
            });
        }
    }
    //Here goes M part
    Map<Integer, Double> avg = new HashMap<>();
    for (Integer key : counts.keySet()) {
        avg.put(key, sums.get(key) / (double) counts.get(key));
    }
    return avg;
}

Output:

{1=0.5, 2=3.0, 3=1.0, 4=3.0, 5=2.0, 6=9.0}

Answer 2

I think from a pure CS standpoint, you can't do any better than you currently do.

Things you may want to look at are your datastructure and use of it.

1) Something simple might be avoiding .contains() in the following way:

Integer count = elemcount.get(element.getKey());
if(count != null){
    //create new element
}else{
    //add to sum
}

2) Create a help class like this:

public class AverageHelper{
    private int sum = 0;
    private int count = 0;
}

And store instances of this class instead of integers. This way, you don't need to put the value in the hashmap everytime you change a value, and you only need to do one lookup instead of two.

Answer 3

Your code is O(NM) because it iterates through every value, for every id.

You need to iterate through the values once, adding the values to some structure which tracks the sum of every value for every id, and the number of values seen.

This lets you calculate average = (sum_values)/n_values in O(N+M), where N is number of values, M is number of ids.