ps:disjoint_set
Disjoint Set
- 웬만하면 한글 번역된 이름을 먼저 쓰고 싶었는데, 이거는 사용 빈도가 압도적인 번역이 있는 것도 아니고, 번역된 이름들도 다 마음에 들지 않는다. 서로소 집합, 분리 집합 다 어색하고, 그냥 디스조인트 셋 또는 유니온파인드 셋 이렇게 쓰는게 사용 빈도가 더 많아 보인다..
- 설명은 위키를 참고하자.
구현 방법
- 표준적인 구현 방법은 Tree 기반이다 (기본 설명 생략)
- Union을 효율적으로 하는 테크닉으로는 union-by-rank와 union-by-size 가 있다
- Find 할때에는 path compression 테크닉이 사용 가능하다.
- path compression에도 단순한 path compression 외에도 path-splitting과 path-halving이라는 테크닉이 존재한다,
- 시간복잡도는 이렇게 된다.
- Find 연산의 amortized 시간복잡도는
- path compression 이나 union-by-rank/size 중 하나를 구현하면 O(logn)
- path compression 과 union-by-rank/size 를 모두 구현하면 O(α(n))
- α(n)은 상수로 간주해도 별 문제 없다
- Union 연산은, Find 연산을 두번 + 상수 시간 연산이라서 Find의 시간복잡도와 동일하다
- m개의 쿼리를 O(m*α(n)) 에 처리한다고 봐도 무방하다.
- Rem's union-find algorithm이라고 불리는 interleaved 방식의 알고리즘도 있다.
- 두 아이템이 같은 셋인지를 찾기 위해서, 각각에 대해 find를 두번 하는 대신에 두 노드의 lca를 찾는 식으로 처리되기 때문에 좀더 효율적일수 있다고 한다. 모든 노드들이 최종적으로 하나로 합쳐지는 kruskal 알고리즘 등에서 더 효율적이라는 논문이 같이 링크되어 있다.. 하지만, 실제로 구현해서 테스트해본 결과는 그냥 tree기반에 비해 빨라지지 않았다.
- 전력난기준, 그냥:1380ms vs Rem:1388ms
- 그냥 List기반으로 구현하는 방법도 있다.
- 얼핏보면 구현방법이 무식해보이는데, 실제로는 small-to-large 테크닉을 적용함으로써 시간복잡도를 단축시키게 된다.
- Find 연산은 O(1)이다. 그냥 list에 인덱스 접근만 하면 끝이라서 상수시간도 매우 작다
- n번의 Union 연산은 O(nlogn)이 걸린다. (union은 최대 n번까지 할수 있다..)
- m개의 쿼리를 O(m+nlogn)에 처리한다고 봐도 무방하다.
- 문제 풀이 게시글에 시간복잡도를 적을때에는 List기반 구현체를 사용해서 풀었더라도 그냥 O(α(n))으로 표기하도록 하자.
실제 구현
- 원소로는 0 ~ n-1까지의 정수만 갖도록 한다.
- 트리나 그래프를 구현할때와 마찬가지이다. 다른 타입의 데이터를 저장하고 싶다면, 정수-다른타입 간의 매핑을 추가로 만들어서 사용하라.
- 참고: 친구 네트워크
- union 연산의 리턴값은 합쳐진 셋의 루트이다.
- union 연산 후에 합쳐진 셋을 갖고서 처리해야 하는 상황이 빈번해서 이쪽을 리턴하기로 했다
- 이것 말고 다른 후보는 union이 실제로 일어났는지 여부를 True/False로 리턴해주는 것이었다 (union하기 전부터 이미 같은 셋이었으면 False리턴). 이것도 매우 빈번하게 사용되는 정보이긴 해서.. 고민끝에, 이미 같은 셋이었으면 예외를 던지기로 했다.
리턴값은 그냥 무시하면 되지만, 예외를 무시하려면 추가 코드가 필요하다.. 그래서 다시, 같은 셋일경우에 예외를 던질지 여부를 인자로 받는 쪽으로 처리했다. raise_if_same 인자가 그 역할이고 기본값은 False이다.같은 셋일때 예외를 날리는 함수와, 안날리는 함수로 따로 구현하는것도 방법이다. 표준 라이브러리에서도 set의 discard와 remove 함수가 이렇게 구현되어있기도 하다. 함수를 분리하면 인자 값을 체크하는데에 드는 시간을 절약할수 있어서 미세한 속도 향상이 있을수도 있긴 하지만.. 그러나 이렇게까지 나누는것은 코드 라인 낭비인거 같아서 기각.
- union 연산 이후에, 실제로 union이 일어났는지 여부를 리턴하는 함수를 고민끝에 union_if_disjoint 라는 이름으로 제공하기로 했다. 그냥 raise_if_same 인자와 예외를 이용해서 처리하는 것과 비교해서 코드가 많이 짧아지기 때문에, 라이브러리 코드쪽이 길어지더라도 따로 제공하는 쪽으로 했다. 속도도 미세하게 빨라지긴 한다.
- 구현한 방식에 따른 성능은, 문제에 따라서 순위가 막 바뀐다.. 한가지의 최적 구현 방식을 찾기가 어렵다..
- union-by-size 만 구현한 코드가 path compression 까지 적용한 코드보다 더 빠른 경우도 있고, list기반과 tree기반의 속도도 문제에 따라 다르다.
- 일반적으로 union-find 알고리즘에서 프랙티컬하게 가장 최적의 조합이 어떤건지를 실험적으로 찾아보려는 노력들이 많이 있는것 같다. 그러나 결론은 대부분 하나의 최적 알고리즘을 찾기 어렵다는 것으로 결론이 나는것 같다. 어차피 파이썬에서는 또 다를테고..
- 실제 구현은 Tree기반과 List기반을 둘다 구현했다.
- 문제에 따라서 tree가 빠르기도, list가 빠르기도 한다.
- 비교표
| 문제 | n | find횟수 | union횟수 | Tree_old | List_old | Tree | Rem | List | 1등 |
|---|---|---|---|---|---|---|---|---|---|
| 사이클 게임 | 500,000 | 0 | 500,000 | 932ms | 1008ms | 844ms | 772ms | 1024ms | 728ms |
| 11724 | 1,000 | 0 | 500,000 | 1224ms | 956ms | 760ms | 936ms | 600ms | |
| 친구 네트워크 | 200,000 | 0 | 100,000 | 336ms | 412ms | - | - | - | 260ms |
| 통신망 분할 | 100,000 | 300,000 | 100,000 | 404ms | 376ms | - | - | - | 344ms |
| 방 청소 | 300,000 | 600,000 | 300,000 | 984ms | 1168ms | 968ms | - | - | 740ms |
| 전력난 | 200,000 | 0 | 200,000 | - | - | 1380ms | 1388ms | - | 1172ms |
| 도시 분할 계획 | 100,000 | 0 | 1,000,000 | 2368ms | - | 2248ms | 2744ms | 2216ms | 2248ms |
- 대체적으로는 find가 많으면 list기반이 좀더 빠르게 동작하는 것 같다. (union이 n번 이상이면, 나머지는 find만 하고 끝나는 것임). 그런데 막상 그래서 두가지 구현이 시간차이가 엄청 크게 나는 문제가 있냐 하면 딱히 그런건 없다. 그냥 아무거나 하나만 구현해놓고 써도 문제 푸는데에 별 지장은 없는것 같다. 그냥 웬만하면 Tree기반 구현을 사용하자.
- Kruskal 알고리즘을 사용하는 graph.minimum_spanning_tree 코드도 내부적으로 그냥 DisjointSet을 사용하도록 구현함.
Tree 기반 구현
- path compression 과 union-by-size를 적용해서 구현했다
- union-by-rank와 union-by-size 어느쪽이든 속도향상을 위해서는 비슷하다고 알려져있지만, size를 알고 있는 것이 활용도가 더 높아서 이쪽으로 구현했다.
- union-by-size의 구현 방법에서는 parent 배열 외에 size 배열을 따로 만들어서 쓸수도 있지만, kks 블로그에 나온 팁을 적용해서, parent 배열에 size에 음수를 취한 값을 저장하는 식으로 해결했다. 메모리 사용이 절반으로 줄어든다!
- path compression은, 일반적으로 좀더 효율적이라고 알려져있는 path splitting을 적용했다.
- 그냥 path compression을 하면, 재귀를 쓰든 루프를 두번 돌려서 구현해야 하는데 path splitting이나 path halving은 한번의 루프로 동작한다. 코드도 더 짧다.
List 기반 구현
- union 할때에 업데이트해줘야 하는것은 nodes_by_set 배열과 set_by_node 배열이다. set_by_node는 일일히 업데이트 해줘야 하므로 전체 복잡도는 어차피 O(n)이지만.. nodes_by_set 배열의 업데이트는 배열대신 링크드리스트와 같은 형태를 쓴다면 O(1)로 줄일수는 있다. 그러나 실험해본 결과.. 억세스하는데에 시간이 추가로 걸리기 때문에, 전체적으로 더 빨라지진 않았다.
- 메모리 사용량은 Tree기반보다 많다. nodes_by_set 배열을 업데이트할때, y셋의 리스트의 원소들을 x셋의 리스트로 옮겨야 하는데, 이쪽에서 pop 하면서 저쪽에서 append 하더라도 메모리를 바로 반환하는게 아니라서.. 그냥 메모리가 추가할당되기만 한다. 그래서 구현도 그냥 pop을 안해버리도록 해버렸다.
- 코드는 여기 - teflib.disjointset.ListDisjointSet
사용팁
- 변수 이름은 dsu로 하자. disjoint_set은 너무 길고, ds는 너무 짧고;
- dsu = disjointset.DisjointSet(N)
- find()로 리턴받은 값들은 xx_set 으로 변수명을 저장하는게 무난하다. 두 셋을 union한 셋은 merged_set으로 변수명을 지어주자 (unioned_set은 좀 어색하다..)
활용
- Offline Range Mimimum Query(RMQ) 를 O(α(n)*(n+q))에 해결하기
- 방법은 여기 참조.
- 관련 문제
ps/disjoint_set.txt · 마지막으로 수정됨: 2022/11/07 14:06 저자 teferi
토론