# Average of multiple vectors with different length

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.

• It should be O(N) as you need to interate only once
– Antoniossss
May 31, 2017 at 18:48
• @Antoniossss how can I iterate only once, if I need to iterate over all values in the outer map and then once more over all in the inner map?
– Cap
May 31, 2017 at 18:54
• @Cap from data sample your profile is a simple Map<Integer,Integer> and you want to get the avarage values in all profiles (maps) am I correct?
– Antoniossss
May 31, 2017 at 18:55
• @Antoniossss not average IN all profile, but average OF all profiles, like in example. If p1={1->1, 2->3, 4->5, 6->9} and p2={1->0, 3->1, 4->1,5->2} then the average is {1->0.5, 2->3, 3->1, 4->3, 5->2, 6->9}.
– Cap
May 31, 2017 at 19:00
• @GhostCat will post there from next time. Didn't know about that sub-platform.
– Cap
May 31, 2017 at 19:01

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}
• I think you forgot to account for the inner loop.
– Thijs Steel
May 31, 2017 at 19:37
• @ThijsSteel no, the fact that you see nested loops, does not mean that complexity will be exponential. Think about it - I could change loop body into x.get(1), x.get(2) .... will that make complexity grater then O(N) ? No. Every element in every profile is looped only once , thus O(N).
– Antoniossss
May 31, 2017 at 19:38
• never said exponential. And the fact that there are nested loops indeed does not imply kwadratic behaviour. But if each profile has a lot of values, that cannot be ignored.
– Thijs Steel
May 31, 2017 at 19:41
• woops, didn't see that you defined N as number of actual values, not the profiles, sorry, you are correct
– Thijs Steel
May 31, 2017 at 19:42
• @ThijsSteel yep, its easier that way because we dont have to worry about different profiles lenghts.in O() calculations.
– Antoniossss
May 31, 2017 at 19:45

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{
}

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.

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.

• I don't get how this results in less operations. The current code is O(N*M), N being the number of profiles, M being the number of values per profile. That's just how many values there are, can't do any faster than that.
– Thijs Steel
May 31, 2017 at 19:03
• @ThijsSteel probably, the question was not understood right. It cannot be O(N) as far as I see.
– Cap
May 31, 2017 at 19:06
• @Antoniossss explains correctly it should be O(N+M).
– Jerry Zhao
May 31, 2017 at 19:58