表信息聚合

Question

我有以下情形：

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

用户是组的一部分，并且组的用户的关系是许多一对多（用户可以属于多个组和一组可以包含多个用户）。任务特定于组中的用户。

有一个List<Task>我需要总结每个用户在一个组中的成功任务数并发送更新给用户。所以，如果一个用户属于几个组，我需要为他的每个组更新一次，他属于（对于该组用户具有的成功任务的数量）。

实现该目标的最佳方法是什么？我们目前的算法是：

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

有没有更好的方法来做到这一点？以上看起来有点容易出错，尤其是最后一次用户检查。

Answer 1

您可以创建一个Pair类，该类将具有User和Group作为最终字段。确保Pair覆盖hashCode()和equals()。

创建一个HashMap<Pair,Integer>，并在迭代列表时维护它[作为直方图]。 [只需要一次传递]。

后来，迭代直方图，并为每Pair发送更新[这实际上是一个元组：(User,Group)]用钥匙 - 包含成功的运行。

应该是这个样子：伪代码，可能会有一些错误syntatic ...]：

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

该解决方案是渐近快则建议的解决方案，因为它不要求排序 - 这样的总运行时间为O(n)。 [而问题中提出的算法是O(nlogn)]。
另外：我觉得这个解决方案更容易理解，但可能是一个见仁见智......

Answer 2

我会说用户对象应该有一个任务列表。 Task对象应该只有id，purpose和isSuccessfull。

Answer 3

如果有人有兴趣，有在Guava一类叫做Multiset这是极好的这个场景。它计算一个元素被输入到集合中的次数。因此，基于Amit的答案：

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