계수의 수는

Question

나는의 형태로 데이터가 :

ID 및 Attr의 정렬되지 않은이며, 중복 포함 할 수

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

. ID의 범위는 1 - 20,000 정도이며 ATTR은 부호없는 int입니다. 한 번에 처리해야하는 10 만 ~ 50 만 쌍이있을 수 있습니다.

1. 고유 한 쌍의 수를 :

   내가 찾고 있어요.

2. 고유하지 않은 쌍이 튀어 나오는 횟수입니다.

위의 데이터에서 (1,20)은 두 번 나타나고 세 개의 고유 한 쌍이 있음을 알고 싶습니다.

저는 현재 순진한 방식으로 해시 테이블을 사용하고 있습니다. 고유 한 쌍의 카운터를 유지하고 삽입하려는 항목이 이미있는 경우 카운터를 감소시킵니다. 또한 고유하지 않은 쌍의 ID 배열을 유지합니다. (처음 만남 전체)

성능과 크기는 거의 같습니다. 실제로 성능과 크기에 대한 우려를 감안할 때 오 탐율이 비교적 높은 (0.5 %) 오 탐지율은 괜찮습니다. (나는 또한 스펙트럼 블룸을 사용하여 이것을 구현했습니다.)

저는 더 똑똑하지가 않아서 더 나은 해결책이 있다는 것을 확신합니다. 좋아하는 해시 테이블 구현에 대해 듣고 싶습니다. 다른 아이디어. :)

Answer 1

<id>=<attr>과 같은 키가있는 해시 테이블은이 문제에 대한 훌륭한 해결책입니다. 실수를 용인 할 수 있다면, 꽃이 피고 작아 지거나 빠를 수 있습니다. 하지만 정말로해야합니까?