뮤텍스 처리
뮤텍스 세트에서만 작동합니다.
이 경우 교차점은 제외됩니다.
노조를 지원하는 작업은 다음과 같습니다.
■ 제작팀 (x) : 요소 x만 포함하는 집합을 만듭니다.
■ lookup_set(x) : 요소 x가 있는 집합을 찾습니다.
■ 합집합(x,y) : 요소 x를 포함하는 집합과 요소 y를 포함하는 집합의 합집합을 만듭니다.
컬렉션을 처리하는 방법에는 연결 목록을 사용하는 방법과 트리를 사용하는 방법의 두 가지가 있습니다.
- 연결된 목록다음을 사용하여 뮤텍스 세트를 처리하는 방법 알아보기
- 연결된 목록처리 집합을 사용하는 작업의 실행 시간을 분석합니다.
- 나무다음을 사용하여 뮤텍스 세트를 처리하는 방법 알아보기
- 나무처리 집합을 사용하는 작업의 실행 시간을 분석합니다.
연결 목록 처리 사용
동일한 컬렉션의 요소는 단일 연결 목록으로 관리됩니다.
연결된 목록의 첫 번째 요소는 집합의 대표 요소입니다.
1) Make-Set 상태(x)
Make-Set(x): 요소 x만 포함하는 집합을 생성합니다.
이때 대표 노드는 자기 자신이 된다.
2) Find-Set(x) 상태
lookup_set(x) : 요소 x가 있는 집합을 찾습니다.
위의 다이어그램에서 컬렉션은 두 부분으로 나눌 수 있습니다.
상위 연결 리스트를 A, 하위 연결 리스트를 B라고 하자.
세트의 각 노드는 첫 번째 노드를 대표 노드로 가리킵니다.
3) 조인트(x,y) 상태
Union(x,y): 요소 x를 포함하는 집합과 요소 y를 포함하는 집합의 합집합을 만듭니다.
이 경우 집합 A는 부분 집합이고 집합 B는 주 집합이라고 가정합니다.
부분 집합 A를 기본 집합 B에 추가하고 집합 A의 각 노드는 노드를 나타내는 포인터를 가리킵니다.
집합 B의 대표 노드로 교체합니다.
NIL을 가리키는 세트 B의 마지막 노드는 세트 A의 헤드 노드입니다.
가리키고 연결하다
노조는 왜 이러는 걸까? 가중 합집합 방법 왜냐하면.
가중치를 고려한다는 것은 연결된 목록의 두 세트를 결합할 때 더 작은 세트가 더 큰 세트 다음에 오는 것을 의미합니다.
그 이유는 조인되는 컬렉션의 대표 요소에 대한 포인터 업데이트 작업을 최소화하기 위함입니다.
4) 수행시간
연결 리스트로 표현되는 배타적 집합에서 가중 합집합을 사용할 때, m개의 Make-Set, Union, Find-Set 중 n개가 Make-Set이면 총 실행 시간은 O(m+nlogn)입니다.
