1
\$\begingroup\$

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.

\$\endgroup\$

migrated from stackoverflow.com May 31 '17 at 20:32

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ It should be O(N) as you need to interate only once \$\endgroup\$ – Antoniossss May 31 '17 at 18:48
  • \$\begingroup\$ @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? \$\endgroup\$ – Cap May 31 '17 at 18:54
  • \$\begingroup\$ @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? \$\endgroup\$ – Antoniossss May 31 '17 at 18:55
  • \$\begingroup\$ @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}. \$\endgroup\$ – Cap May 31 '17 at 19:00
  • \$\begingroup\$ @GhostCat will post there from next time. Didn't know about that sub-platform. \$\endgroup\$ – Cap May 31 '17 at 19:01
0
\$\begingroup\$

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}
\$\endgroup\$
  • \$\begingroup\$ I think you forgot to account for the inner loop. \$\endgroup\$ – Thijs Steel May 31 '17 at 19:37
  • \$\begingroup\$ @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). \$\endgroup\$ – Antoniossss May 31 '17 at 19:38
  • \$\begingroup\$ 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. \$\endgroup\$ – Thijs Steel May 31 '17 at 19:41
  • \$\begingroup\$ woops, didn't see that you defined N as number of actual values, not the profiles, sorry, you are correct \$\endgroup\$ – Thijs Steel May 31 '17 at 19:42
  • \$\begingroup\$ @ThijsSteel yep, its easier that way because we dont have to worry about different profiles lenghts.in O() calculations. \$\endgroup\$ – Antoniossss May 31 '17 at 19:45
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Thijs Steel May 31 '17 at 19:03
  • \$\begingroup\$ @ThijsSteel probably, the question was not understood right. It cannot be O(N) as far as I see. \$\endgroup\$ – Cap May 31 '17 at 19:06
  • \$\begingroup\$ @Antoniossss explains correctly it should be O(N+M). \$\endgroup\$ – Jerry Zhao May 31 '17 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.