表信息聚合

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