Подсчет количества уникальных пар и экземпляров неуникальных пар в несортированных данных

Question

У меня есть данные в виде:

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

Где ID и Attr не отсортированы и могут содержать дубликаты.Диапазон для идентификаторов 1-20 000 или около того, и ATTR без знака int.Может быть где-то между 100 000 и 500 000 пар, которые мне нужно обработать за один раз.

Я ищу:

1. Количество уникальных пар.
2. Количество раз, когда появляется неуникальная пара.

Итак, в приведенных выше данных я хотел бы знать, что (1,20) появилось дважды и что было 3 уникальных пары.

В настоящее время я использую хэш-таблицу в своем наивном подходе.Я держу счетчик уникальных пар и уменьшаю его, если элемент, который я вставляю, уже есть.Я также храню массив идентификаторов неуникальных пар.(Все при первых встречах)

Производительность и размер примерно одинаковы.Я на самом деле в порядке с относительно высоким (скажем, 0,5%) количеством ложных срабатываний, учитывая проблемы производительности и размера.(Я также реализовал это, используя спектральное расцветание)

Я не настолько умен, поэтому я уверен, что есть лучшее решение, и я хотел бы услышать о ваших любимых реализациях хеш-таблиц/ любые другие идеи.:)

Answer 1

Хеш-таблица с ключами типа <id>=<attr> является отличным решением этой проблемы.Если вы можете терпеть ошибки, вы можете стать меньше / быстрее с цветением, я думаю.Но тебе действительно нужно это сделать?