큰 데이터를위한 분리 세트

Question

큰 데이터 (예 : 2^32 개 이상의 요소와 2^32 개 이상의 조합)에 향상된 분리 세트 알고리즘이 있습니까?

분명히 가장 큰 문제는 큰 배열을 만들 수 없다는 것이므로 더 나은 알고리즘이나 더 나은 데이터 구조가 내 작업을 수행 할 수 있는지 궁금합니다.

Answer 1

정말 큰 데이터를 처리하는 한 가지 방법은 외부 메모리에있는 것을 실행하는 것입니다. http://terrain.cs.duke.edu/pubs/union-find.pdf (I/O 효율적인 배치 일괄 검색 및 지형 분석에 대한 적용)에는 다른 일괄 처리 알고리즘에 대한 호출이 상당히 복잡한 시퀀스로 구성된 이론적 알고리즘과 (3 장) 자체 포함 순환 알고리즘이 있습니다. 점근 적으로 효율적이지는 않지만 실용적인 것처럼 보입니다.