2

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.

3 Answers 3

2

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...

1
  • Thanks, I was going in this direction too but your code is better. Speed is less of a concern here but I also think this solution is cleaner and easier to understand.
    – Alex
    Mar 20, 2012 at 20:25
0

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

1
  • Unfortunately I can't really change the class design
    – Alex
    Mar 20, 2012 at 10:30
0

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));
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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