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

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>是解决这个问题的绝佳方法。如果你能容忍错误，我想你可以通过绽放变得更小/更快。但你真的需要这样做吗？