데이터 세트에서 고유 한 목록을 만들어 메모리에 저장하기에 너무 크다

Question

각각 약 40/50 바이트의 약 1 억 2 천만 레코드 목록을 보유하고 있습니다.이 메모리는 약 5.5/6 기가 바이트의 원시 메모리 공간으로 메모리에 배열.

이 목록이 고유한지 확인하고 싶습니다. 내가 시도한 방식은 Hashset < 문자열 >을 생성하고 하나씩 차례로 모든 항목을 추가하는 것입니다.

약 3 천 3 백만 건의 레코드가 생기면 나는 기억이 나지 않아 목록 생성이 느려지 게됩니다.

이 대량의 항목을시기 적절하게 정렬하는 더 좋은 방법이 있습니까? 내가 생각할 수있는 유일한 해결책은 Amazon EC2 하이 - 메모리 쿼드 러플 엑스트라 라지 인스턴스를 1 시간 동안 사용하는 것입니다. 그냥 고유성을 확인하려는 경우

감사

Answer 1

, 나는 단순히 버킷으로 입력 순서를 분할 한 다음 개별적으로 각 버킷을 확인합니다.

예를 들어, 파일의 데이터를로드한다고 가정하면 입력을 스트리밍하고 26 개의 다른 파일에 기록 할 수 있습니다. 하나는 각 문자가 시작하는 문자입니다 (각 레코드를 순진하게 가정합니다). AZ로 시작 - 실제 상황에 맞게 조정하십시오). 그런 다음 작은 파일들 각각을 기존 코드와 같은 것을 사용하여 독창성을 검사 할 수 있습니다 - 그 중 어느 것도 너무 커서 한 번에 메모리에 맞지 않을 수 있습니다. 초기 버킷 팅은 서로 다른 버킷에 중복 된 항목이 없음을 보장합니다.

물론 버킷을 수행 할 수있는 다양한 방법이 있으며, 다양한 데이터 세트에 대해 서로 다른 접근 방식이 효과적입니다. 예를 들어 해시 코드로 버킷을 만들 수 있습니다. 해시 코드의 하단 5 비트를 가져 와서 32 개의 버킷을 만듭니다. 그럴 경우 은 합리적으로 버켓간에 레코드가 균등하게 분배되며 입력 데이터에 대해 어떠한 가정도하지 않습니다. 나는 개념을 파악하는 더 간단한 방법이므로 위의 "첫 번째 문자 접근법"을 언급했습니다.

Answer 2

을 사용하여 버킷의 내용 중 일부를 디스크에 정기적으로 플러시하여 주기적으로 버리지 않도록합니다 메모리의. 그런 다음 플러시 된 각 버킷을 순서대로로드하고 HashSet 접근 방식을 사용하거나 정렬하여 확인하십시오.

Answer 3

데이터 집합에 대한 추가 처리에 도움이 될 수 있으므로 항상 고유 인덱스가있는 sqlite 데이터베이스에서 작업 할 수 있습니다.