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

我有以下forms的数据：

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

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

我在寻找：

1. 唯一对的数量。
2. 弹出非唯一对的次数。

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

我目前正在使用我的天真方法中的哈希表。 我保留一个唯一对的计数器，如果我插入的项目已经存在，则递减计数器。 我还保留了一组非唯一对的ID。 （所有初次见面时）

性能和尺寸大致相同。 考虑到性能和尺寸问题，我实际上可以获得相对较高（假设为0.5％）的误报率。 （我也使用频谱绽放实现了这个）

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

Answer 1

具有=类的键的哈希表是解决此问题的绝佳解决方案。 如果你可以容忍错误，我猜你会变得更小/更快。 但你真的需要这样做吗？