CODEWITHSUNDEEP
javaalgorithmlist
Alex
Alex

Reputation: 1131

List information aggregation

I have the following scenario:

class Task {
    int id;
    Group group;
    User user;
    boolean successful;
}

User is part of Group, and Group-User relationship is many-to-many (user may belong to multiple groups and a group may contain multiple users). Task is specific to a User in a Group.

There is a List<Task> for which I need to summarize the number of successful tasks per User in a Group and send update to the user. So, if a user belongs to several groups I need to update him once for each group he belongs to (with the number of successful tasks the user had for that group).

What would be the best way to achieve that? Our current algorithm is:

First, sort the list by Group ID and then by User ID.
Then: 

int successfulTasks = 0;
Group curGroup = null;
User curUser = null;
for(Task task : tasksByGroupAndUser) {
    if((task.getGroup() != curGroup) || (task.getUser() != curUser) {
        // Going to next user or group, update the previous user
        updateUser(user,group, successfulTasks);
        successfulTasks = 0;        
    }

    if(task.isSuccessful()) {
        successfulTasks++;
    }
}

// Handle last user  
if(curUser != null) {
    updateUser(user,group, successfulTasks); 
}

Is there a better (cleaner) way to do this? The above seems somewhat error-prone, especially that last user check.

Upvotes: 2

Views: 150

Answers (3)

Alex
Alex

Reputation: 1131

In case anyone is interested, there is a class in Guava called Multiset that is excellent for this scenario. It counts the number of times an element has been entered into the set. So, based on amit's answer:

Multiset<Pair> histogram = new HashMultiset<Pair>(); // Pair is a tuple of (User,Group)
for(Task task : tasksByGroupAndUser) {
   if (task.isSuccessful()) {
      Pair current = new Pair(task.getUser(),task.getGroup());
      histogram.add(current);
   }
}
for (Pair pair : histogram) { 
   updateUser(pair.getUser(),pair.getGroup(),histogram.count(entry));
}

Upvotes: 0

amit
amit

Reputation: 178481

You can create a Pair class which will have User and Group as final fields. Make sure Pair overrides hashCode() and equals().

Create a HashMap<Pair,Integer>, and maintain it [as a histogram] while iterating the list. [Need only one pass on the list for that].

Later, iterate the histogram, and send an update for every Pair [which is actually a tuple: (User,Group)] with the key - containing succesful runs.

Should look something like: [Pseudo-code, there might be some syntatic errors...]:

Map<Pair,Integer> histogram = new HashMap<Pair,Integer>();
for(Task task : tasksByGroupAndUser) {
   if (task.isSuccessful() == false) continue; //just skip unseccessful tasks.
   Pair current = new Pair(task.getUser(),task.getGroup());
   Integer value = histogram.get(current);
   histogram.put(current, value == null? 1 : value + 1); //update the histogram
}
for (Entry<Pair,Integer> entry : histogram.entrySet()) { 
   updateUser(entry.getKey().getUser(),entry.getKey().getGroup(),entry.getValue());
}

This solution is asymptotically faster then the suggested solution since it is not requires sorting - so the total runtime is O(n). [while the algorithm suggested in the question is O(nlogn)].
Also: I find this solution easier to understand, but that might be a matter of opinion...

Upvotes: 2

Noroi
Noroi

Reputation: 71

I would say the User object should have a List of tasks. The Task object should only have the id, purpose and isSuccessfull.

Upvotes: 0

Related Questions