큰 수의 큰 파일에서 중복을 제거하는 방법은 무엇입니까? 이것은 sort -u이 아닌 알고리즘 및 데이터 구조에 관한 인터뷰 질문입니다.파일에서 중복 항목을 제거하는 방법은 무엇입니까?
파일이 메모리에 들어 가지 않으며 숫자 범위가 충분히 커서 인 - 메모리 개수/버킷 정렬을 사용할 수 없다고 가정합니다.
유일한 옵션은 파일을 정렬 (예 : merge sort)하고 분류 된 파일을 다시 전달하여 중복 파일을 필터링하는 것입니다.
의미가 있습니다. 다른 옵션이 있습니까?
예, 해결책이 있습니다.
다른 대안은 파일 시스템 기반 해시 테이블을 작성하고이를 세트로 유지하는 것입니다. 먼저 모든 요소를 반복하여 세트에 삽입 한 다음 나중에 두 번째 반복에서 세트의 모든 요소를 인쇄하십시오.
이 병합 정렬 옵션이 더 안정 O(nlogn) 솔루션을 제공하면서 큰-O 복잡성의 측면에서 더 나은 수행 구현 및 데이터 종속, 해시, O(n) 시간 평균 케이스와 O(n^2) 최악의 경우를 제공합니다.
"merge"(a.k.a. "union") 중복 복제 제거 변형을 사용하는 경우 정렬 된 데이터를 별도로 전달할 필요가 없습니다. 해시 테이블은 파일 자체보다 크고 성능이 좋은 비어 있어야하며 파일 자체는 이라고합니다.
다중 방향 병합 (예 : here) 및 외부 정렬을 찾습니다.
개선 된 mergesort 인 Mergesort 또는 Timsort가 좋습니다. 예 : http://stromberg.dnsalias.org/~strombrg/sort-comparison/
블룸 필터에서 약간의 주행 거리를 얻을 수도 있습니다. 낮은 메모리 요구 사항을 가진 확률 론적 데이터 구조입니다. 블룸 필터를 사용하여 오류 확률을 조정할 수 있습니다. EG : http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/ 하나를 사용하여 확실히 고유 한 값을 버리고 다른 방법을 통해 좀 더 자세히 알려지지 않은 값을 면밀히 조사 할 수 있습니다. 입력 데이터 집합에 많은 중복이있는 경우 특히 유용합니다. 요소를 직접 비교할 필요가 없으며 잠재적으로 많은 수의 해시 함수를 사용하여 요소를 해시합니다.
디스크상의 BTree 또는 2-3 트리 또는 유사한 것을 사용할 수도 있습니다. 이들은 종종 디스크에 저장되며 키/값 쌍을 주요 순서로 유지합니다.
입력에 대해 더 많이 알수록 알맞은 알고리즘을 선택/개발할 수있는 위치가 좋습니다. – greybeard