计算未排序数据中唯一对的数量和非唯一对的实例

我有以下形式的数据:

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

其中 ID 和 Attr 未排序并且可能包含重复项。 ID 的范围是 1-20,000 左右，ATTR 是 unsigned int。我可能需要一次处理 100,000 到 500,000 对之间的任何地方。

我在寻找:

唯一对的数量。

非唯一对弹出的次数。

所以在上面的数据中，我想知道 (1,20) 出现了两次并且有 3 个独特的对。

我目前在我的天真方法中使用哈希表。我保留一个唯一对的计数器，如果我插入的项目已经存在，则递减计数器。我还保留了一组非唯一对的 ID。 (都是第一次见面)

性能和大小是同等关注的问题。考虑到性能和大小问题，我实际上可以接受相对较高(比如 0.5%)的误报率。 (我也使用光谱绽放实现了这一点)

我不是那么聪明，所以我相信那里有更好的解决方案，我想听听你最喜欢的哈希表实现/任何其他想法。 :)

最佳答案

带有 <id>=<attr> 之类的键的哈希表是解决此问题的绝佳方法。如果你能容忍错误，你可以通过绽放变得更小/更快，我猜。但你真的需要这样做吗？

关于计算未排序数据中唯一对的数量和非唯一对的实例，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7549410/