Union-Find in Linux | Linux 6.18.37

요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.

1. 요약·해설

원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.

요약과 해설

union_find.rst:1-106

Union-find는 element를 서로소 set으로 관리하면서 root representative를 찾고 두 set을 병합합니다. Dynamic connectivity, graph algorithm, register allocation 등에 적합합니다.

Linux 구현은 `lib/union_find.c`와 `<linux/union_find.h>`에 있으며, `struct uf_node`의 `parent`와 `rank`로 forest를 표현합니다.

`uf_find()`는 path compression으로 이후 탐색을 단축하고, `uf_union()`은 rank가 작은 tree를 큰 tree 아래에 연결해 높이를 제한합니다. 평균 operation 비용은 실용적으로 상수에 가까운 `O(α(n))`입니다.

2. 영어 원문 전체

번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.

원문 전체 펼치기

1 .. SPDX-License-Identifier: GPL-2.0

3 ====================

4 Union-Find in Linux

5 ====================

8 :Date: June 21, 2024

9 :Author: Xavier <[email protected]>

11 What is union-find, and what is it used for?

12 ------------------------------------------------

14 Union-find is a data structure used to handle the merging and querying

15 of disjoint sets. The primary operations supported by union-find are:

17 Initialization: Resetting each element as an individual set, with

18 each set's initial parent node pointing to itself.

20 Find: Determine which set a particular element belongs to, usually by

21 returning a “representative element” of that set. This operation

22 is used to check if two elements are in the same set.

24 Union: Merge two sets into one.

26 As a data structure used to maintain sets (groups), union-find is commonly

27 utilized to solve problems related to offline queries, dynamic connectivity,

28 and graph theory. It is also a key component in Kruskal's algorithm for

29 computing the minimum spanning tree, which is crucial in scenarios like

30 network routing. Consequently, union-find is widely referenced. Additionally,

31 union-find has applications in symbolic computation, register allocation,

32 and more.

34 Space Complexity: O(n), where n is the number of nodes.

36 Time Complexity: Using path compression can reduce the time complexity of

37 the find operation, and using union by rank can reduce the time complexity

38 of the union operation. These optimizations reduce the average time

39 complexity of each find and union operation to O(α(n)), where α(n) is the

40 inverse Ackermann function. This can be roughly considered a constant time

41 complexity for practical purposes.

43 This document covers use of the Linux union-find implementation. For more

44 information on the nature and implementation of union-find, see:

46 Wikipedia entry on union-find

47 https://en.wikipedia.org/wiki/Disjoint-set_data_structure

49 Linux implementation of union-find

50 -----------------------------------

52 Linux's union-find implementation resides in the file "lib/union_find.c".

53 To use it, "#include <linux/union_find.h>".

55 The union-find data structure is defined as follows::

57 struct uf_node {

58 struct uf_node *parent;

59 unsigned int rank;

60 };

62 In this structure, parent points to the parent node of the current node.

63 The rank field represents the height of the current tree. During a union

64 operation, the tree with the smaller rank is attached under the tree with the

65 larger rank to maintain balance.

67 Initializing union-find

68 -----------------------

70 You can complete the initialization using either static or initialization

71 interface. Initialize the parent pointer to point to itself and set the rank

72 to 0.

73 Example::

75 struct uf_node my_node = UF_INIT_NODE(my_node);

77 or

79 uf_node_init(&my_node);

81 Find the Root Node of union-find

82 --------------------------------

84 This operation is mainly used to determine whether two nodes belong to the same

85 set in the union-find. If they have the same root, they are in the same set.

86 During the find operation, path compression is performed to improve the

87 efficiency of subsequent find operations.

88 Example::

90 int connected;

91 struct uf_node *root1 = uf_find(&node_1);

92 struct uf_node *root2 = uf_find(&node_2);

93 if (root1 == root2)

94 connected = 1;

95 else

96 connected = 0;

98 Union Two Sets in union-find

99 ----------------------------

100

101 To union two sets in the union-find, you first find their respective root nodes

102 and then link the smaller node to the larger node based on the rank of the root

103 nodes.

104 Example::

105

106 uf_union(&node_1, &node_2);

107

3. 한국어 전문 번역

영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.

Linux의 Union-Find

1-10

SPDX License Identifier: `GPL-2.0`

Linux의 Union-Find

날짜: 2024년 6월 21일

저자: Xavier <[email protected]>

Union-find란 무엇이며 어디에 사용하는가

11-48

Union-find란 무엇이며 어디에 사용하는가?

Union-find는 서로소 집합의 병합과 질의를 처리하는 data structure입니다. Union-find가 지원하는 주요 operation은 다음과 같습니다.

Initialization: 각 element를 개별 set으로 reset하고 각 set의 초기 parent node가 자기 자신을 가리키게 합니다.
Find: 특정 element가 속한 set을 판별하며, 보통 그 set의 representative element를 반환합니다. 두 element가 같은 set에 있는지 확인하는 데 사용합니다.
Union: 두 set을 하나로 병합합니다.

Set 또는 group을 유지하는 data structure인 union-find는 offline query, dynamic connectivity 및 graph theory 관련 문제를 푸는 데 흔히 사용합니다. Network routing 같은 시나리오에 중요한 minimum spanning tree를 계산하는 Kruskal algorithm의 핵심 component이기도 하므로 널리 참조됩니다.

Union-find는 symbolic computation과 register allocation 등에도 응용됩니다.

Space Complexity: node 수를 n이라 할 때 `O(n)`입니다.

Time Complexity: path compression은 find operation의 time complexity를 줄이고 union by rank는 union operation의 time complexity를 줄입니다. 이러한 최적화를 사용하면 각 find와 union operation의 평균 time complexity는 `O(α(n))`이 됩니다. 여기서 `α(n)`은 inverse Ackermann function이며, 실제 용도에서는 대략 constant time complexity로 볼 수 있습니다.

이 문서는 Linux union-find implementation의 사용법을 다룹니다. Union-find의 성질과 구현에 관한 자세한 내용은 Wikipedia의 union-find 항목을 참조하십시오.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Linux union-find 구현

49-66

Linux union-find 구현

Linux의 union-find implementation은 `lib/union_find.c` file에 있습니다. 사용하려면 `#include <linux/union_find.h>`를 추가하십시오.

Union-find data structure는 다음과 같이 정의됩니다.

struct uf_node {
        struct uf_node *parent;
        unsigned int rank;
};

이 structure에서 `parent`는 현재 node의 parent node를 가리킵니다. `rank` field는 현재 tree의 height를 나타냅니다. Union operation 중에는 balance를 유지하도록 rank가 작은 tree를 rank가 큰 tree 아래에 붙입니다.

Union-find 초기화

67-80

Union-find 초기화

Static interface 또는 initialization interface 중 하나를 사용해 초기화할 수 있습니다. Parent pointer가 자기 자신을 가리키게 하고 rank를 0으로 설정합니다.

예:

struct uf_node my_node = UF_INIT_NODE(my_node);

또는

uf_node_init(&my_node);

Union-find root node 찾기

81-97

Union-find root node 찾기

이 operation은 주로 union-find의 두 node가 같은 set에 속하는지 판별하는 데 사용합니다. Root가 같으면 같은 set에 있습니다. Find operation 중에는 이후 find operation의 효율을 높이기 위해 path compression을 수행합니다.

예:

int connected;
struct uf_node *root1 = uf_find(&node_1);
struct uf_node *root2 = uf_find(&node_2);
if (root1 == root2)
        connected = 1;
else
        connected = 0;

Union-find의 두 set 병합

98-106

Union-find의 두 set 병합

Union-find에서 두 set을 병합하려면 먼저 각각의 root node를 찾은 다음 root node의 rank를 기준으로 작은 node를 큰 node에 연결합니다.

예:

uf_union(&node_1, &node_2);