2 개 이상의 요소를 공유하는 세트 병합 알고리즘

StackOverflow https://stackoverflow.com/questions/312912

  •  10-07-2019
  •  | 
  •  

문제

세트 목록이 주어지면 :

  • S_1 : [1, 2, 3, 4
  • S_2 : [3, 4, 5, 6, 7
  • S_3 : [8, 9, 10, 11
  • S_4 : [1, 8, 12, 13
  • S_5 : [6, 7, 14, 15, 16, 17

최소 2 개 이상의 요소를 공유하는 모든 세트를 병합하는 가장 효율적인 방법은 무엇입니까? 이것이 연결된 구성 요소 문제와 유사하다고 생각합니다. 결과는 다음과 같습니다.

  • 1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 Union S_2 Union S_5)
  • [ 8, 9, 10, 11 ]
  • 1, 8, 12, 13] (S_4는 S_1과 1, S_3의 8 주를 주식하지만 각각 하나의 요소 만 공유하기 때문에 합병되지 않음)

순진한 구현은 O (n^2)이며, 여기서 n은 세트의 수이며, 우리에게는 불가능합니다. 이것은 수백만 세트에 효율적이어야합니다.

도움이 되었습니까?

해결책 

Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

내 머리는 이것이 질서에 관한 것이라고 말하고있다 (2n ln n). 소금 한 알로 가져 가십시오.

다른 팁

세트에서 요소를 주문할 수 있다면 사용을 살펴볼 수 있습니다. MERGESORT 세트에. 필요한 수정은 병합 단계에서 복제물을 확인하는 것입니다. 하나를 찾으면 복제본을 버리십시오. Mergesort는 O (n*log (n))이므로 순진한 O (n^2) 알고리즘과 비교할 때 IMRPOVED 속도를 제공합니다.

그러나 실제로 효과적이기 위해서는 정렬 된 세트를 유지하고 정렬을 유지하여 정렬 단계를 건너 뛰고 병합 단계로 바로 이동할 수 있도록해야합니다.

나는 이것이 어떻게 O (n^2)에서 어떻게 할 수 있는지 알지 못한다.

모든 세트는 2 개 이상의 공유 요소를 포함하는지 확인하려면 다른 모든 세트와 비교해야합니다. 공유 요소에 대한 검사에 일정한 시간이 걸리더라도 N*(N-1)/2 비교이므로 O (N^2)입니다.

정렬 할 때 순진한 구현은 O (n^2)이지만 순서 비교의 전이 특성을 활용할 수 있습니다 (예를 들어, QuickSort의 낮은 파티션에서 상단 파티션의 어떤 것도 비교할 필요가 없습니다. , 이미 피벗과 비교되었으므로). 이것이 O (n * log n) 인 분류를 초래하는 것입니다.

여기에는 적용되지 않습니다. 따라서 이전 비교 결과에 따라 비교를 건너 뛸 수있는 세트에 대한 특별한 것이 없다면 일반적으로 O (n^2)가 될 것입니다.

폴.

한 가지 참고 사항 : 이것이 얼마나 자주 발생하는지에 따라 다릅니다. 대부분의 세트 쌍 인 경우 하다 적어도 두 가지 요소를 공유하면 비교를 밟는 것과 동시에 새 세트를 구축하는 것이 가장 효율적일 수 있으며 조건과 일치하지 않으면 버리십시오. 대부분의 쌍 인 경우 하지 마라 적어도 두 가지 요소를 공유 한 다음 조건의 확인이 더 효율적일 때까지 새 세트의 건물을 연기하십시오.

요소가 본질적으로 수치 적이거나 자연스럽게 주문할 수 있다면 (예 : 1, 2, 42 등과 같은 값을 할당 할 수 있습니다 ...) 병합 된 세트에 라디습니다. 고유 한 요소를 픽업하기 위해 통과하십시오.

이 알고리즘은 O (n)이어야하며 비트 시프트 연산자 및 비트 마스크를 사용하여 Radix 정렬을 약간 최적화 할 수 있습니다. 나는 내가 작업하고있는 프로젝트에 대해 비슷한 일을했으며, 그것은 매력처럼 작동합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top