計數數目

Question

我有形式的數據：

ID ATTR 
3 10 
1 20 
1 20 
4 30 
... ... 

其中ID和的Attr是未排序並且可能包含重複。 ID的範圍是1-20,000左右，而ATTR是無符號整數。我可能需要一次處理100,000到500,000對之間的任何地方。

我要找：

1. 獨特對的數目。
2. 非唯一對彈出的次數。

所以在上面的數據中，我想知道（1,20）出現了兩次，並且有3個獨特的對。

我目前在我的天真方法中使用哈希表。我保留一個唯一對的計數器，如果我插入的項目已經存在，則遞減計數器。我還保留了非唯一對的ID數組。 （所有在第一次遭遇）

表現和大小是關於同等關切。實際上，考慮到性能和尺寸方面的問題，相對較高（假設爲0.5％）的誤報率。 （我也實現了這個使用頻譜布盧姆）

我不是那麼聰明，所以我敢肯定有更好的解決方案，我想聽聽你最喜歡的哈希表實現/任何其他想法。 :)

Answer 1

帶有諸如<id>=<attr>之類鍵的散列表是解決此問題的絕佳解決方案。如果你可以容忍錯誤，我想你可以花更多的時間更快更快。但你真的需要這樣做嗎？