Union-Find 기반 증분 연결성 추적
Union-Find, 또는 Disjoint Set Union은 여러 원소가 어떤 연결 컴포넌트에 속하는지를 추적하는 자료구조다. 처음에는 각 원소가 독립된 집합이고, union(a, b)가 두 집합을 합치며, find(a)가 원소가 속한 집합의 대표 루트(root)를 찾는다.
· 연습 메모 · 48 min read · Medium
Union-Find, 또는 Disjoint Set Union은 여러 원소가 어떤 연결 컴포넌트에 속하는지를 추적하는 자료구조다. 처음에는 각 원소가 독립된 집합이고, union(a, b)가 두 집합을 합치며, find(a)가 원소가 속한 집합의 대표 루트(root)를 찾는다.
단순히 parent만 연결하면 입력 순서에 따라 긴 사슬이 만들어질 수 있는데, 이번 구현은 작은 트리를 큰 트리 아래에 붙이는 union-by-size와, root를 찾는 동안 중간 노드를 조부모 쪽으로 당기는 path halving을 함께 사용한다.
생성 비용까지 포함하면 N개 원소를 만들고 m번 연산하는 비용은 O(N + m α(N))이다.
원소 생성도 m에 포함하거나 m ≥ N으로 두면 보통 O(m α(N))으로 쓴다. 연산당 상각 비용은 O(α(N))이며, 개별 연산의 최악 시간이 항상 O(1)이라는 뜻은 아니라는 점을 알 수 있다.
여기서 역 Ackermann 계열 상각 상한 출처는 구분하자면, Tarjan의 1975년 결과는 path compression과 union-by-size 조합을 분석하였다.1
여기서 쓰는 path halving은 그 논문의 분석 대상이 아니며,
Tarjan과 van Leeuwen은 이후 union-by-size 또는 rank와 compression, splitting, halving의 각 조합이 같은 점근 상한을 가진다는 것을 보였다는 것을 알 수 있다.2(솔직히 이 문장은 아직도 헷갈리지만, 논문에서는 그렇다고 한다.)
이 구조의 진짜 장점은 연결 관계 전체를 graph 객체로 반복 탐색하지 않고, 조밀한 정수 배열 두 개로 연결성 질문에 답한다는 점이다. 네트워크 endpoint, 이미지 영역, 계정 병합 후보, Kruskal 최소 신장 트리처럼 연결이 추가되기만 하는 문제에 적합하다.
여기서 트레이드 오프는 기능의 제한이며, Union-Find는 두 원소가 연결되었는지는 알려주지만 실제 연결 경로는 알려주지 않는다.
또한 edge 삭제로 컴포넌트가 갈라지는 상황을 직접 처리하지 못한다. 삭제가 필요하면 재구축, rollback DSU를 사용하는 offline 처리, 또는 동적 연결성 자료구조가 필요하다.
Union-Find
= Parent Forest
+ Union-by-Size
+ Path Halving
find(x)
= x가 속한 집합의 root
union(a, b)
= root(a)와 root(b)가 다르면
작은 컴포넌트를 큰 컴포넌트 아래에 연결
connected(a, b)
= find(a) == find(b)
핵심 불변식:
root인 원소:
parent[root] == root
모든 원소:
parent를 반복해서 따라가면
정확히 하나의 root에 도달
componentSize[root]
= 해당 root가 대표하는 원소 수1. 문제 상황
서버 간 연결 정보가 순차적으로 들어오는 네트워크 관리 시스템을 생각하자.
서버:
0, 1, 2, 3, 4, 5
신규 연결:
0 — 1
1 — 2
3 — 4
2 — 4처음에는 모든 서버가 독립 컴포넌트다.
{0} {1} {2} {3} {4} {5}0—1, 1—2를 반영하면 다음과 같다.
{0, 1, 2} {3} {4} {5}3—4를 반영하면 다음과 같다.
{0, 1, 2} {3, 4} {5}마지막으로 2—4를 반영하면 두 컴포넌트가 합쳐진다.
{0, 1, 2, 3, 4} {5}필요한 핵심들:
0과 4는 연결되어 있는가?
→ true
0과 5는 연결되어 있는가?
→ false
3이 속한 컴포넌트 크기는?
→ 5
현재 독립 컴포넌트 수는?
→ 2이번 구현은 원소 ID가 0..N-1인 조밀한 정수라고 가정한다. UUID나 문자열 ID는 호출 경계에서 정수 index로 변환한다.
2. 핵심 표현
실패를 다루는 방식
이 문서의 public API는 원소 수와 node 범위, 외부 서버 ID, snapshot 적재처럼 호출자가 처리할 수 있는 실패를 예외로 던지지 않는다. 각 구현은 성공 값 T 또는 오류 값을 가진 배타적인 Result 계열 타입을 사용한다.
TypeScript는 오류형 E까지 제네릭으로 두고, C++, Python, C# 예제는 DisjointSetError를 고정 오류형으로 사용한다.
생성은 create 또는 Create factory로만 열어 두고, 실패한 생성은 빈 객체나 부분 초기화된 객체를 만들지 않는다.
connect()의 false는 오류가 아니다. 두 node가 이미 같은 컴포넌트였다는 정상 결과다. 반면 invalid-node와 invalid-element-count는 호출부가 입력을 고치거나 요청을 거부해야 하는 명시적 실패다. 메모리 고갈, 런타임 자체의 결함, private helper의 전제 위반은 이 오류 모델에 억지로 넣지 않는다.
성공 값과 오류 값은 동시에 존재할 수 없다는 대전제를 바탕으로 작업해야한다.
C++는 std::variant, TypeScript는 discriminated union, Python은 Success | Failure, C#은 Result<T>.SuccessCase | FailureCase로 이 배타 상태를 표현한다.
버전과 검증 환경
구현 | 코드가 요구하는 기준 | 이 문서에서 확인한 환경 |
|---|---|---|
C++ | C++20. | MSYS2 UCRT64 g++ 16.1.0, |
Python | Python 3.7 이상. | Python 3.14.6 실행 |
C# | C# 10 이상. |
|
TypeScript | private field와 discriminated union을 지원하는 TypeScript, | TypeScript 7.0.2, Node.js 24.18.0 실행 |
- 구현
C++
- 코드가 요구하는 기준
C++20.
std::variant와std::optional사용- 이 문서에서 확인한 환경
MSYS2 UCRT64 g++ 16.1.0,
-std=c++20 -Wall -Wextra -Werror -pedantic문법 검사
- 구현
Python
- 코드가 요구하는 기준
Python 3.7 이상.
from __future__ import annotations,dataclasses,typing사용- 이 문서에서 확인한 환경
Python 3.14.6 실행
- 구현
C#
- 코드가 요구하는 기준
C# 10 이상.
record struct사용- 이 문서에서 확인한 환경
net8.0target, .NET SDK 10.0.302 Release 실행
- 구현
TypeScript
- 코드가 요구하는 기준
private field와 discriminated union을 지원하는 TypeScript,
node:test실행에는 Node.js 18 이상- 이 문서에서 확인한 환경
TypeScript 7.0.2, Node.js 24.18.0 실행
C++20에는 표준 expected가 없으므로 여기서는 작은 Result<T>를 문서 안에 정의했다.
프로젝트가 C++23을 기준으로 한다면 같은 계약을 std::expected<T, DisjointSetError>로 옮길 수 있다.
C++20
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <optional>
#include <utility>
#include <variant>
#include <vector>
enum class DisjointSetErrorCode
{
invalidElementCount,
invalidNode,
};
struct DisjointSetError
{
DisjointSetErrorCode code;
std::size_t value;
};
template <typename T>
class [[nodiscard]] Result final
{
public:
[[nodiscard]]
static Result success(T value)
{
return Result(std::move(value));
}
[[nodiscard]]
static Result failure(DisjointSetError error)
{
return Result(error);
}
[[nodiscard]]
bool isSuccess() const noexcept
{
return std::holds_alternative<T>(storage_);
}
[[nodiscard]]
const T& value() const&
{
return std::get<T>(storage_);
}
[[nodiscard]]
T&& takeValue() &&
{
return std::get<T>(std::move(storage_));
}
[[nodiscard]]
const DisjointSetError& error() const&
{
return std::get<DisjointSetError>(storage_);
}
private:
explicit Result(T value)
: storage_(std::move(value))
{
}
explicit Result(DisjointSetError error)
: storage_(error)
{
}
std::variant<T, DisjointSetError> storage_;
};
class DisjointSet final
{
public:
[[nodiscard]]
static Result<DisjointSet> create(
std::size_t elementCount)
{
if (const auto error = elementCountError(elementCount);
error.has_value())
{
return Result<DisjointSet>::failure(*error);
}
return Result<DisjointSet>::success(
DisjointSet(elementCount));
}
[[nodiscard]]
Result<bool> connect(
std::uint32_t left,
std::uint32_t right)
{
if (const auto error = validateNode(left);
error.has_value())
{
return Result<bool>::failure(*error);
}
if (const auto error = validateNode(right);
error.has_value())
{
return Result<bool>::failure(*error);
}
std::uint32_t leftRoot = findRoot(left);
std::uint32_t rightRoot = findRoot(right);
if (leftRoot == rightRoot)
{
return Result<bool>::success(false);
}
attachSmallerRoot(leftRoot, rightRoot);
componentCount_ -= 1;
return Result<bool>::success(true);
}
[[nodiscard]]
Result<bool> areConnected(
std::uint32_t left,
std::uint32_t right)
{
if (const auto error = validateNode(left);
error.has_value())
{
return Result<bool>::failure(*error);
}
if (const auto error = validateNode(right);
error.has_value())
{
return Result<bool>::failure(*error);
}
return Result<bool>::success(
findRoot(left) == findRoot(right));
}
[[nodiscard]]
Result<std::uint32_t> getComponentSize(
std::uint32_t node)
{
if (const auto error = validateNode(node);
error.has_value())
{
return Result<std::uint32_t>::failure(*error);
}
return Result<std::uint32_t>::success(
componentSize_[findRoot(node)]);
}
[[nodiscard]]
std::size_t getComponentCount() const noexcept
{
return componentCount_;
}
[[nodiscard]]
std::size_t getElementCount() const noexcept
{
return parent_.size();
}
private:
static constexpr std::size_t maximumElementCount =
10'000'000;
explicit DisjointSet(std::size_t elementCount)
: parent_(elementCount),
componentSize_(elementCount, 1),
componentCount_(elementCount)
{
std::iota(
parent_.begin(),
parent_.end(),
std::uint32_t{0});
}
std::vector<std::uint32_t> parent_;
std::vector<std::uint32_t> componentSize_;
std::size_t componentCount_;
[[nodiscard]]
std::uint32_t findRoot(std::uint32_t node)
{
while (parent_[node] != node)
{
parent_[node] = parent_[parent_[node]];
node = parent_[node];
}
return node;
}
void attachSmallerRoot(
std::uint32_t leftRoot,
std::uint32_t rightRoot)
{
if (componentSize_[leftRoot]
< componentSize_[rightRoot])
{
std::swap(leftRoot, rightRoot);
}
parent_[rightRoot] = leftRoot;
componentSize_[leftRoot] +=
componentSize_[rightRoot];
}
[[nodiscard]]
std::optional<DisjointSetError> validateNode(
std::uint32_t node) const
{
if (node >= parent_.size())
{
return DisjointSetError{
DisjointSetErrorCode::invalidNode,
node,
};
}
return std::nullopt;
}
[[nodiscard]]
static std::optional<DisjointSetError>
elementCountError(std::size_t elementCount)
{
if (elementCount == 0
|| elementCount > maximumElementCount)
{
return DisjointSetError{
DisjointSetErrorCode::invalidElementCount,
elementCount,
};
}
return std::nullopt;
}
};사용:
auto topologyResult = DisjointSet::create(6);
if (!topologyResult.isSuccess())
{
return handle(topologyResult.error());
}
DisjointSet topology =
std::move(topologyResult).takeValue();
for (const auto pair : {
std::pair{0U, 1U},
std::pair{1U, 2U},
std::pair{3U, 4U},
std::pair{2U, 4U},
})
{
const auto merged = topology.connect(
pair.first,
pair.second);
if (!merged.isSuccess())
{
return handle(merged.error());
}
}
const auto connected = topology.areConnected(0, 4);
const auto groupSize = topology.getComponentSize(3);areConnected()와 getComponentSize()는 둘 다 내부적으로 findRoot()를 거치므로 논리적으로는 질의지만 물리적으로는 배열을 수정한다.
그래서 const 메서드가 아니라는 걸 알 수 있다.
검증 실패는 Result의 오류 값으로 돌아온다. false는 여전히 "이미 같은 컴포넌트였다"는 정상 결과이며, 오류와 섞이지 않는다. nodiscard는 호출부가 성공과 실패를 확인하도록 강제한다.
생성자 초기화 순서
검증을 생성자 본문에 두면 vector 두 개의 할당을 시도한 뒤다. componentCount_는 size_t 값 하나라 별도 동적 할당이 없다.
explicit DisjointSet(std::size_t elementCount)
: parent_(elementCount),
componentSize_(elementCount, 1),
componentCount_(elementCount)
{
validateElementCount(elementCount); // 너무 늦다.
}elementCount가 20억이면 오류 값을 만들기도 전에 이미 할당을 시도한다. 이 문서의 create()는 먼저 elementCountError()를 확인한 뒤, 검증된 값으로만 private 생성자를 호출한다.
멤버는 초기화 목록에 적은 순서가 아니라 클래스 본문의 선언 순서로 초기화된다. 현재 코드는 모든 초기화 식에서 검증된 elementCount를 직접 사용하므로 이 순서에 의존하지 않는다. 그래도 멤버 순서를 바꿀 때 이 규칙을 알아야 하는 이유는 다음과 같다.
위 코드가 componentSize_(parent_.size(), 1)에서 parent_를 읽을 수 있는 이유는 초기화 식의 첫 자리에 적었기 때문이 아니라, 선언이 다음 순서이기 때문이라는 것을 명심하자.
std::vector<std::uint32_t> parent_;
std::vector<std::uint32_t> componentSize_;
std::size_t componentCount_;초기화 목록의 순서가 멤버 선언 순서와 다르면 GCC와 Clang은 보통 -Wreorder를 경고한다.3이 문서의 검증 옵션처럼 -Werror를 함께 쓰면 그 경고는 빌드 오류가 된다. 그러나 아직 생성되지 않은 다른 멤버를 초기화 식에서 참조하는 오류까지 항상 진단해 준다는 보장은 없다. 따라서 parent_.size()보다 검증된 elementCount를 직접 쓰는 편이 안전하다.
GCC와 Clang은 보통 -Wreorder 경고를 내는데, 이 문서의 검증 옵션처럼 -Werror를 함께 쓰면 그 경고는 빌드 오류가 된다. 선언 순서에 기대고 싶지 않다면 초기화 식에서 elementCount를 직접 쓰거나, 검증된 값을 받는 위임 생성자를 두는 것이 좋다.
Python
from __future__ import annotations
from dataclasses import dataclass
from typing import Generic, Optional, TypeVar, Union
T = TypeVar("T")
@dataclass(frozen=True)
class DisjointSetError:
code: str
value: object
@dataclass(frozen=True)
class Success(Generic[T]):
value: T
@dataclass(frozen=True)
class Failure:
error: DisjointSetError
Result = Union[Success[T], Failure]
class DisjointSet:
_MAXIMUM_ELEMENT_COUNT = 10_000_000
@classmethod
def create(
cls,
element_count: object,
) -> Result[DisjointSet]:
error = _element_count_error(
element_count,
cls._MAXIMUM_ELEMENT_COUNT,
)
if error is not None:
return Failure(error)
return Success(cls(int(element_count)))
def __init__(self, element_count: int) -> None:
self._parent = list(range(element_count))
self._component_size = [1] * element_count
self._component_count = element_count
def connect(
self,
left: object,
right: object,
) -> Result[bool]:
left_error = self._node_error(left)
if left_error is not None:
return Failure(left_error)
right_error = self._node_error(right)
if right_error is not None:
return Failure(right_error)
left_root = self._find_root(int(left))
right_root = self._find_root(int(right))
if left_root == right_root:
return Success(False)
self._attach_smaller_root(left_root, right_root)
self._component_count -= 1
return Success(True)
def are_connected(
self,
left: object,
right: object,
) -> Result[bool]:
left_error = self._node_error(left)
if left_error is not None:
return Failure(left_error)
right_error = self._node_error(right)
if right_error is not None:
return Failure(right_error)
return Success(
self._find_root(int(left))
== self._find_root(int(right))
)
def get_component_size(
self,
node: object,
) -> Result[int]:
error = self._node_error(node)
if error is not None:
return Failure(error)
root = self._find_root(int(node))
return Success(self._component_size[root])
def get_component_count(self) -> int:
return self._component_count
def get_element_count(self) -> int:
return len(self._parent)
def _find_root(self, node: int) -> int:
while self._parent[node] != node:
self._parent[node] = self._parent[
self._parent[node]
]
node = self._parent[node]
return node
def _attach_smaller_root(
self,
left_root: int,
right_root: int,
) -> None:
if (
self._component_size[left_root]
< self._component_size[right_root]
):
left_root, right_root = right_root, left_root
self._parent[right_root] = left_root
self._component_size[left_root] += (
self._component_size[right_root]
)
def _node_error(
self,
node: object,
) -> Optional[DisjointSetError]:
if not _is_integer(node):
return DisjointSetError("invalid_node", node)
integer_node = int(node)
if (
integer_node < 0
or integer_node >= len(self._parent)
):
return DisjointSetError("invalid_node", node)
return None
def _element_count_error(
element_count: object,
maximum_element_count: int,
) -> Optional[DisjointSetError]:
if not _is_integer(element_count):
return DisjointSetError(
"invalid_element_count",
element_count,
)
if (
int(element_count) < 1
or int(element_count) > maximum_element_count
):
return DisjointSetError(
"invalid_element_count",
element_count,
)
return None
def _is_integer(value: object) -> bool:
return isinstance(value, int) and not isinstance(value, bool)사용:
created = DisjointSet.create(6)
if isinstance(created, Failure):
handle(created.error)
else:
topology = created.value
for left, right in [(0, 1), (1, 2), (3, 4), (2, 4)]:
merged = topology.connect(left, right)
if isinstance(merged, Failure):
handle(merged.error)
connected = topology.are_connected(0, 4)
group_size = topology.get_component_size(3)재귀적 find() 대신 반복문을 사용했다. 트리가 예상보다 깊어져도 Python 호출 스택 한도에 의존하지 않기때문이다. 다만 parent 배열의 cycle 같은 불변식 위반을 복구하거나 감지하는 것은 별도 책임이다.
_is_integer()가 bool을 따로 거부하는 이유는 Python에서 bool이 int의 하위 타입이기 때문이다. isinstance(True, int)는 참이므로 이 검사를 빼면 DisjointSet.create(True)가 원소 하나짜리 집합을 만들고, connect(True, False)가 connect(1, 0)으로 조용히 통과한다.
이 구현은 두 입력을 모두 Failure로 돌려준다.(기본적으로 이 부분은
C#
using System;
public enum DisjointSetErrorCode
{
InvalidElementCount,
InvalidNode,
}
public readonly record struct DisjointSetError(
DisjointSetErrorCode Code,
int Value);
public abstract class Result<T>
{
private Result()
{
}
public sealed class SuccessCase : Result<T>
{
public SuccessCase(T value)
{
this.Value = value;
}
public T Value { get; }
}
public sealed class FailureCase : Result<T>
{
public FailureCase(DisjointSetError error)
{
this.Error = error;
}
public DisjointSetError Error { get; }
}
public static Result<T> Success(T value)
{
return new SuccessCase(value);
}
public static Result<T> Failure(
DisjointSetError error)
{
return new FailureCase(error);
}
}
public sealed class DisjointSet
{
private const int MaximumElementCount =
10_000_000;
private readonly int[] parent;
private readonly int[] componentSize;
private int componentCount;
private DisjointSet(int elementCount)
{
this.parent = new int[elementCount];
this.componentSize = new int[elementCount];
this.componentCount = elementCount;
this.InitializeElements();
}
public static Result<DisjointSet> Create(
int elementCount)
{
if (elementCount is < 1
or > MaximumElementCount)
{
return Result<DisjointSet>.Failure(
new DisjointSetError(
DisjointSetErrorCode.InvalidElementCount,
elementCount));
}
return Result<DisjointSet>.Success(
new DisjointSet(elementCount));
}
public Result<bool> Connect(
int left,
int right)
{
if (this.GetNodeError(left) is { } leftError)
{
return Result<bool>.Failure(leftError);
}
if (this.GetNodeError(right) is { } rightError)
{
return Result<bool>.Failure(rightError);
}
int leftRoot = this.FindRoot(left);
int rightRoot = this.FindRoot(right);
if (leftRoot == rightRoot)
{
return Result<bool>.Success(false);
}
this.AttachSmallerRoot(leftRoot, rightRoot);
this.componentCount -= 1;
return Result<bool>.Success(true);
}
public Result<bool> AreConnected(
int left,
int right)
{
if (this.GetNodeError(left) is { } leftError)
{
return Result<bool>.Failure(leftError);
}
if (this.GetNodeError(right) is { } rightError)
{
return Result<bool>.Failure(rightError);
}
return Result<bool>.Success(
this.FindRoot(left) == this.FindRoot(right));
}
public Result<int> GetComponentSize(int node)
{
if (this.GetNodeError(node) is { } error)
{
return Result<int>.Failure(error);
}
return Result<int>.Success(
this.componentSize[this.FindRoot(node)]);
}
public int GetComponentCount()
{
return this.componentCount;
}
public int GetElementCount()
{
return this.parent.Length;
}
private int FindRoot(int node)
{
while (this.parent[node] != node)
{
this.parent[node] =
this.parent[this.parent[node]];
node = this.parent[node];
}
return node;
}
private void AttachSmallerRoot(
int leftRoot,
int rightRoot)
{
if (this.componentSize[leftRoot]
< this.componentSize[rightRoot])
{
(leftRoot, rightRoot) =
(rightRoot, leftRoot);
}
this.parent[rightRoot] = leftRoot;
this.componentSize[leftRoot] +=
this.componentSize[rightRoot];
}
private void InitializeElements()
{
for (
int index = 0;
index < this.parent.Length;
index += 1)
{
this.parent[index] = index;
this.componentSize[index] = 1;
}
}
private DisjointSetError? GetNodeError(int node)
{
if (node < 0 || node >= this.parent.Length)
{
return new DisjointSetError(
DisjointSetErrorCode.InvalidNode,
node);
}
return null;
}
}사용방법:
Result<DisjointSet> created = DisjointSet.Create(6);
if (created is Result<DisjointSet>.FailureCase failed)
{
return Handle(failed.Error);
}
DisjointSet topology =
((Result<DisjointSet>.SuccessCase)created).Value;
foreach ((int left, int right) in new[]
{
(0, 1),
(1, 2),
(3, 4),
(2, 4),
})
{
Result<bool> merged = topology.Connect(left, right);
if (merged is Result<bool>.FailureCase failedMerge)
{
return Handle(failedMerge.Error);
}
}
Result<bool> connected =
topology.AreConnected(0, 4);
Result<int> groupSize =
topology.GetComponentSize(3);componentSize는 root 위치에서만 의미가 있다.
외부 코드가 배열을 직접 읽지 못하게 캡슐화하고, 항상 FindRoot()를 거쳐 조회해야한다.
C#은 Create()가 배열을 만들기 전에 원소 수를 검사하는데. private 생성자는 검증된 값만 받으므로 예상 가능한 입력 오류를 예외로 던지지 않는다.
공개 API에서 명시적 실패를 반환하는 설계와, 내부 반복에서 할당을 피하는 설계는 분리해야 한다. (이는 API 설계의 기본이지만 여전히 지키기 어렵다)
공개 경계에서는 현재의 variant 표현을 유지한다. 성공과 실패를 동시에 담을 수 없는 형태라 호출부가 잘못된 상태를 만들기 어렵기 때문이다라고 할 수 있다.
현재 Connect() 한 번은 참조형 결과 하나를 만드는데, 그러나 FindRoot()와 AttachSmallerRoot()는 결과 객체를 만들지 않는다. 따라서 ConnectUnchecked()로 단순 분리해도 공개 Connect()가 Result<bool>를 반환하는 한 할당 수는 줄지 않는다.
이미 검증된 index를 대량 처리하는 내부 batch 작업이 생기면 그때 ConnectUnchecked()를 추가한다. 해당 batch가 helper를 직접 호출할 때만 Result를 만들지 않는 경로가 생긴다.
프로파일링에서 공개 API의 결과 객체 할당이 실제 병목으로 확인되면, 내부 batch 경로를 두거나 Merged, AlreadyConnected, InvalidInput enum과 out DisjointSetError 계약으로 API를 바꾸는 선택지가 있다. 후자는 할당을 줄일 수 있지만 범용 Result<T>의 균일한 오류 전달 방식을 포기하는 설계 변경이다. 값 타입 Result<T>도 만능이 아니다. default(Result<T>)와 잘못된 tag, value, error 조합을 허용할 수 있다.
이게 프로그래밍의 짜증나는 점이다. 뭐 하나 자잘한거 몇개 쓰는데 다른 개발자가 어떻게 읽을지, 내가 어떻게 생각했는지 하나하나 기술해야하는 이 사실이 짜증나낟.
TypeScript
export type DisjointSetError = Readonly<{
code: "invalid-element-count" | "invalid-node";
value: number;
}>;
export type Result<T, E = DisjointSetError> =
| Readonly<{ ok: true; value: T }>
| Readonly<{ ok: false; error: E }>;
export function success<T, E = never>(
value: T,
): Result<T, E>
{
return { ok: true, value };
}
export function failure<T = never, E = never>(
error: E,
): Result<T, E>
{
return { ok: false, error };
}
export class DisjointSet
{
static readonly #maximumElementCount =
10_000_000;
readonly #parent: Int32Array;
readonly #componentSize: Int32Array;
#componentCount: number;
public static create(
elementCount: number,
): Result<DisjointSet>
{
const error = validateElementCount(
elementCount,
DisjointSet.#maximumElementCount,
);
if (error !== undefined) {
return failure(error);
}
return success(new DisjointSet(elementCount));
}
private constructor(elementCount: number)
{
this.#parent = new Int32Array(elementCount);
this.#componentSize =
new Int32Array(elementCount);
this.#componentCount = elementCount;
this.#initializeElements();
}
public connect(
left: number,
right: number,
): Result<boolean>
{
const leftError = this.#nodeError(left);
if (leftError !== undefined) {
return failure(leftError);
}
const rightError = this.#nodeError(right);
if (rightError !== undefined) {
return failure(rightError);
}
const leftRoot = this.#findRoot(left);
const rightRoot = this.#findRoot(right);
if (leftRoot === rightRoot) {
return success(false);
}
this.#attachSmallerRoot(leftRoot, rightRoot);
this.#componentCount -= 1;
return success(true);
}
public areConnected(
left: number,
right: number,
): Result<boolean>
{
const leftError = this.#nodeError(left);
if (leftError !== undefined) {
return failure(leftError);
}
const rightError = this.#nodeError(right);
if (rightError !== undefined) {
return failure(rightError);
}
return success(
this.#findRoot(left)
=== this.#findRoot(right),
);
}
public getComponentSize(
node: number,
): Result<number>
{
const error = this.#nodeError(node);
if (error !== undefined) {
return failure(error);
}
return success(
this.#componentSize[this.#findRoot(node)],
);
}
public getComponentCount(): number
{
return this.#componentCount;
}
public getElementCount(): number
{
return this.#parent.length;
}
#findRoot(node: number): number
{
while (this.#parent[node] !== node) {
this.#parent[node] =
this.#parent[this.#parent[node]];
node = this.#parent[node];
}
return node;
}
#attachSmallerRoot(
leftRoot: number,
rightRoot: number,
): void
{
if (this.#componentSize[leftRoot]
< this.#componentSize[rightRoot]) {
[leftRoot, rightRoot] = [rightRoot, leftRoot];
}
this.#parent[rightRoot] = leftRoot;
this.#componentSize[leftRoot] +=
this.#componentSize[rightRoot];
}
#initializeElements(): void
{
for (
let index = 0;
index < this.#parent.length;
index += 1
) {
this.#parent[index] = index;
this.#componentSize[index] = 1;
}
}
#nodeError(
node: number,
): DisjointSetError | undefined
{
if (!Number.isSafeInteger(node)
|| node < 0
|| node >= this.#parent.length) {
return {
code: "invalid-node",
value: node,
};
}
return undefined;
}
}
export function validateElementCount(
elementCount: number,
maximumElementCount: number,
): DisjointSetError | undefined
{
if (!Number.isSafeInteger(elementCount)
|| elementCount < 1
|| elementCount > maximumElementCount) {
return {
code: "invalid-element-count",
value: elementCount,
};
}
return undefined;
}Int32Array를 사용해 일반 number[]보다 저장 형식과 element width를 명확하게 고정했다. 이번 상한에서는 component size와 parent index가 signed 32-bit 범위를 넘지 않는다고 본다.
이 코드는 --strict와 --noUnusedLocals를 기준으로 작성했다.
--noUncheckedIndexedAccess를 켜면 typed array 인덱싱도 number | undefined로 취급될 수 있다. 그 설정을 쓰는 프로젝트라면 #nodeError() 뒤의 값을 지역 변수로 좁혀야 한다. 범위 검증을 했다는 사실을 컴파일러가 배열 접근까지 자동으로 전파하지는 않는다.
같은 크기의 두 트리
attachSmallerRoot()의 비교는 <이므로 두 컴포넌트의 크기가 같을 때는 swap이 일어나지 않고 right가 left 아래로 들어간다. 크기가 같으면 어느 쪽을 root로 삼아도 결과 트리의 높이 상한이 같으므로 이 tie-break는 임의로 정해도 된다. <=로 바꿔도 정확성과 상각 복잡도는 그대로다.
다만은 root가 어느 쪽으로 정해지는지는 바뀌므로, 테스트가 특정 root 값을 기대하고 있다면 그 테스트가 잘못된 것을 검증하고 있다는 신호라고 할 수 있다.
3. 호출부
외부 서버 ID는 문자열이므로 별도의 index 계층에서 조밀한 정수로 변환한다. Union-Find 자체는 문자열, DB, 네트워크 I/O를 알지 못한다.
DisjointSet은 원소 수가 1 이상이라는 계약을 둔다. 그런데 빈 snapshot은 오류가 아니라 정상 결과이므로, 호출부는 DisjointSet.create() 전에 빈 index를 돌려주는 분기를 둔다. 이 경우를 DisjointSet | null 필드로 섞으면 조회 경로마다 절대 참이 되지 않는 null 검사가 남는다. 노드 맵이 비어 있으면 requireNode()가 unknown-server-id 오류를 돌려준다. 구현을 둘로 나누면 그 분기가 조회 경로에서 사라진다.
import {
DisjointSet,
failure,
success,
type DisjointSetError,
type Result,
} from "./ds.ts";
export type NetworkLink = Readonly<{
leftServerId: string;
rightServerId: string;
}>;
export type NetworkSnapshot = Readonly<{
serverIds: readonly string[];
links: AsyncIterable<NetworkLink>;
}>;
export type SnapshotReadError = Readonly<{
code: "snapshot-read-failed";
cause: unknown;
}>;
export type ConnectivityError =
| DisjointSetError
| SnapshotReadError
| Readonly<{
code: "invalid-server-id"
| "duplicated-server-id"
| "unknown-server-id";
serverId: string;
}>
| Readonly<{
code: "aborted";
}>
| Readonly<{
code: "link-stream-failed";
cause: unknown;
}>;
type ConnectivityResult<T> =
Result<T, ConnectivityError>;
export type NetworkSource = Readonly<{
readSnapshotAsync: (
signal?: AbortSignal,
) => Promise<Result<NetworkSnapshot, SnapshotReadError>>;
}>;
export interface ConnectivityIndex
{
areConnected(
leftServerId: string,
rightServerId: string,
): ConnectivityResult<boolean>;
getComponentSize(
serverId: string,
): ConnectivityResult<number>;
getComponentCount(): number;
}
export class EmptyConnectivityIndex
implements ConnectivityIndex
{
public areConnected(
leftServerId: string,
rightServerId: string,
): ConnectivityResult<boolean>
{
const leftError = serverIdError(leftServerId);
if (leftError !== undefined) {
return failure(leftError);
}
const rightError = serverIdError(rightServerId);
if (rightError !== undefined) {
return failure(rightError);
}
return failure({
code: "unknown-server-id",
serverId: leftServerId,
});
}
public getComponentSize(
serverId: string,
): ConnectivityResult<number>
{
const error = serverIdError(serverId);
if (error !== undefined) {
return failure(error);
}
return failure({
code: "unknown-server-id",
serverId,
});
}
public getComponentCount(): number
{
return 0;
}
}
export class ServerConnectivityIndex
implements ConnectivityIndex
{
readonly #nodeByServerId:
ReadonlyMap<string, number>;
readonly #sets: DisjointSet;
public constructor(
nodeByServerId: ReadonlyMap<string, number>,
sets: DisjointSet,
)
{
this.#nodeByServerId = nodeByServerId;
this.#sets = sets;
}
public areConnected(
leftServerId: string,
rightServerId: string,
): ConnectivityResult<boolean>
{
const left = this.#getNode(leftServerId);
if (!left.ok) {
return left;
}
const right = this.#getNode(rightServerId);
if (!right.ok) {
return right;
}
return this.#sets.areConnected(left.value, right.value);
}
public getComponentSize(
serverId: string,
): ConnectivityResult<number>
{
const node = this.#getNode(serverId);
if (!node.ok) {
return node;
}
return this.#sets.getComponentSize(node.value);
}
public getComponentCount(): number
{
return this.#sets.getComponentCount();
}
#getNode(
serverId: string,
): ConnectivityResult<number>
{
return requireNode(
this.#nodeByServerId,
serverId,
);
}
}
export async function buildConnectivityIndexAsync(
source: NetworkSource,
signal?: AbortSignal,
): Promise<ConnectivityResult<ConnectivityIndex>>
{
if (signal?.aborted) {
return failure({ code: "aborted" });
}
let snapshotResult:
Result<NetworkSnapshot, SnapshotReadError>;
try {
snapshotResult = await source.readSnapshotAsync(signal);
} catch (cause) {
if (signal?.aborted) {
return failure({ code: "aborted" });
}
return failure({
code: "snapshot-read-failed",
cause,
});
}
if (signal?.aborted) {
return failure({ code: "aborted" });
}
if (!snapshotResult.ok) {
return failure(snapshotResult.error);
}
const nodeIndex = createNodeIndex(
snapshotResult.value.serverIds,
);
if (!nodeIndex.ok) {
return nodeIndex;
}
if (nodeIndex.value.size === 0) {
return success(new EmptyConnectivityIndex());
}
const setsResult = DisjointSet.create(
nodeIndex.value.size,
);
if (!setsResult.ok) {
return setsResult;
}
try {
for await (const link of snapshotResult.value.links) {
if (signal?.aborted) {
return failure({ code: "aborted" });
}
const connected = connectLink(
setsResult.value,
nodeIndex.value,
link,
);
if (!connected.ok) {
return connected;
}
}
} catch (cause) {
if (signal?.aborted) {
return failure({ code: "aborted" });
}
return failure({
code: "link-stream-failed",
cause,
});
}
if (signal?.aborted) {
return failure({ code: "aborted" });
}
return success(new ServerConnectivityIndex(
nodeIndex.value,
setsResult.value,
));
}
function createNodeIndex(
serverIds: readonly string[],
): ConnectivityResult<ReadonlyMap<string, number>>
{
const index =
new Map<string, number>();
for (const serverId of serverIds) {
const error = serverIdError(serverId);
if (error !== undefined) {
return failure(error);
}
if (index.has(serverId)) {
return failure({
code: "duplicated-server-id",
serverId,
});
}
index.set(serverId, index.size);
}
return success(index);
}
function connectLink(
sets: DisjointSet,
nodes: ReadonlyMap<string, number>,
link: NetworkLink,
): ConnectivityResult<void>
{
const left =
requireNode(nodes, link.leftServerId);
if (!left.ok) {
return left;
}
const right =
requireNode(nodes, link.rightServerId);
if (!right.ok) {
return right;
}
const merged = sets.connect(left.value, right.value);
if (!merged.ok) {
return merged;
}
return success(undefined);
}
function requireNode(
nodes: ReadonlyMap<string, number>,
serverId: string,
): ConnectivityResult<number>
{
const error = serverIdError(serverId);
if (error !== undefined) {
return failure(error);
}
const node = nodes.get(serverId);
if (node === undefined) {
return failure({
code: "unknown-server-id",
serverId,
});
}
return success(node);
}
function serverIdError(
serverId: string,
): ConnectivityError | undefined
{
if (!/^[A-Za-z0-9_.:-]{1,100}$/.test(
serverId,
)) {
return {
code: "invalid-server-id",
serverId,
};
}
return undefined;
}책임 분리에 관해서:
NetworkSource
= 서버와 link snapshot I/O
Node Index
= 외부 문자열 ID
→ 조밀한 정수 index 변환
DisjointSet
= 정수 원소의 연결 컴포넌트 관리
ConnectivityIndex
= 업무 ID 기반 조회 API
Snapshot Builder
= Load → Validate → Map → Union
Rebuild Policy
= link 삭제나 snapshot version 변경 처리Union-Find의 root index를 외부 API에 노출하지 않는다. root는 이후 union에 따라 바뀔 수 있는 내부 구현 정보라고 볼 수 있다.
connectLink()와 #getNode()가 같은 requireNode()를 쓰므로 알 수 없는 서버 ID의 오류 코드가 적재부와 조회부에서 한 곳에 모인다. buildConnectivityIndexAsync()가 Map만 돌려주고 DisjointSet을 지역 변수로 버리면 이름과 달리 연결성 정보가 하나도 남지 않는다. 반환값이 DisjointSet을 수명 안에 붙들고 있어야 한다.
Index의 수명
여기서 실제로 메모리를 지배하는 것은 Union-Find 배열이 아니라 문자열 맵이다.
Node 22에서 36자 ID 100만 개를 Map<string, number>에 넣은 측정에서 약 119.5 MiB라는 값이 나왔었는데, 이는 Node 버전, ID를 만든 시점, full GC 전후 baseline, 실행 옵션에 따라 달라지는 관측값이다.
비교할 때는 측정 축도 분리해야 하는 것.
Map/string delta:
heapUsed 기준 약 119.5 MiB
Int32Array 두 개, 원소 100만 개:
arrayBuffers 기준 약 7.6 MiBheapUsed는 V8 heap을, arrayBuffers는 typed array backing store를 주로 보여준다. 두 수치를 같은 축의 절대값처럼 비교하면 안 된다고 하는데,
재현 가능한 수치를 남기기위해서 Node 버전, 실행 옵션, ID 생성 시점, baseline과 측정 전후의 process.memoryUsage() 필드를 함께 기록해야한다.(생각보다 버전별로 차이가 크다)
ConnectivityIndex를 프로세스 수명 내내 캐싱하면 이 맵도 함께 살아 있으므로, 수명 정책은 자료구조가 아니라 호출부에서 정해야 하는 것이다.
- 요청 단위 인덱스: 응답 후 참조를 끊는다
- 장기 캐시: snapshot version과 TTL을 함께 둔다
- 재구축: 새 인덱스를 만든 뒤 참조를 교체한다
- 조회가 많으면: 검증된 정수 handle을 상위 세션이 들고 있게 한다WeakRef나 FinalizationRegistry로 수명을 흐리게 만들 자리는 아니다. 인덱스는 명시적으로 만들고 명시적으로 버린다.
4. 읽는 순서
원소 ID가 0..N-1로 조밀한가
→ parent[i]가 유효한 index인가
→ 초기 parent[i]가 i인가
→ find가 root까지 이동하는가
→ find 과정에서 경로를 압축하는가
→ union 전에 양쪽 root를 찾는가
→ 이미 같은 root면 상태를 바꾸지 않는가
→ 작은 컴포넌트를 큰 컴포넌트에 붙이는가
→ size는 새 root에만 더하는가
→ componentCount는 실제 병합 때만 감소하는가
→ 크기 검증이 배열 할당보다 먼저 일어나는가
→ root를 외부의 영구 ID로 노출하지 않는가핵심 코드 리뷰 지점:
parent[right] = left가 아니라 다음이어야 한다.
parent[rootOfSmallerComponent]
= rootOfLargerComponent원소 자체가 아니라 대표 root끼리 연결해야 한다.
5. 실제 사용해보면서 생긴 오해 지점
Union-Find는 edge 삭제를 처리하지 못한다
다음 graph에서 1—2를 삭제하면 컴포넌트가 둘로 갈라질 수 있다.
0 — 1 — 2 — 3하지만 Union-Find에는 어떤 edge가 두 집합을 연결했는지에 관한 정보가 없기에, 다음과 같은 선택지가 생긴다.
삭제 대응 선택지:
- 전체 snapshot에서 재구축
- 시간 순서를 뒤집은 offline 처리
- Rollback DSU
- 완전 동적 연결성 자료구조Edge 추가만 있는 workload인지 먼저 확인해야 한다. 임의 삭제를 poly-logarithmic 시간에 처리하는 완전 동적 연결성 자료구조는 Union-Find와 별개의 알고리즘이다.4
실제 연결 경로를 제공하지 않는다
areConnected(0, 7)
→ trueUnion-Find는 0→3→5→7 같은 실제 graph path를 반환하지 않는다. 경로가 필요하면 adjacency graph를 별도로 유지하고 BFS·DFS 등을 수행해야 한다. parent forest는 원래 graph의 간선이 아니라고 한다(GPT의 설명)
Root는 안정적인 컴포넌트 ID가 아니다
현재 다음과 같다고 하자.
root({0, 1, 2}) = 0
root({3, 4, 5, 6}) = 3두 집합을 합치면 union-by-size에 따라 작은 집합의 root가 바뀐다.
union(0, 3)
root({0,1,2,3,4,5,6})
= 3Root를 DB key나 사용자에게 노출되는 group ID로 사용하면 이후 union에서 식별자가 바뀐다. 업무상 안정된 group ID가 필요하면 별도 canonical ID 정책을 둔다.
componentSize[node]는 일반 원소에서 유효하지 않다
병합 후 작은 root의 size 값을 굳이 0으로 만들지 않았다.
parent[2] = 0
componentSize[2] = 과거 값유효한 조회:
componentSize[find(2)]잘못된 조회:
componentSize[2]내부 배열을 외부에 노출하지 않는 이유기도 하다.
find()는 읽기처럼 보여도 쓰기다
경로 압축은 parent를 변경한다.
압축 전:
7 → 5 → 3 → 0
find(7)
압축 후 예:
7 → 3 → 0areConnected()와 getComponentSize()는 이름이 질의처럼 보이지만 둘 다 findRoot()를 거치므로 배열을 수정하는데, 이러한 점을 고려하자면, 여러 thread가 이 두 메서드만 호출해도 동기화 없이 공유하면 데이터 경쟁이 된다. 효율적인 concurrent Union-Find는 배열에 lock 하나를 붙이는 문제보다 복잡하며, 별도의 CAS 기반 알고리즘과 분석이 존재한다.5
사용에대한 운영 정책:
Build 단계:
단일 owner가 union과 path halving 수행
Publish 단계:
모든 경로를 압축한 immutable snapshot 생성
Read 단계:
수정하지 않는 root lookup 사용또는 actor·lock·partitioned ownership을 선택한다.
Rollback과 경로 단축은 잘 맞지 않는다
중요하니까 빨간색으로 적어둔다.
Rollback DSU는 변경 이력을 stack에 기록한 뒤 이전 상태로 되돌린다. path halving을 포함한 경로 단축은 find() 한 번에 여러 parent를 변경하므로 되돌려야 할 기록이 크게 늘어난다.
Rollback이 핵심 요구라면 일반적으로:
- union-by-size 유지
- path halving을 포함한 경로 단축 생략
- 변경된 parent와 size만 stack에 기록상각 성능보다 undo 가능성을 우선한다. 이 조합의 연산당 비용은 O(log N)이 되며, 이는 상각이 아니라 최악 비용이다.
외부 ID를 바로 배열 index로 사용하지 않는다
다음 ID에 맞춰 배열을 만들면 낭비다.
server IDs:
17
8,000,000
2,000,000,000실제 원소는 3개뿐인데 최대 ID 크기에 맞춘 배열이 필요해진다.
외부 ID
→ dense index mapping
→ 0, 1, 2Union-Find의 배열 효율은 index 공간이 조밀할 때 나온다.
중복 union은 실패가 아니라 no-op일 수 있다
connect(0, 1)
connect(0, 1)두 번째 호출은 이미 같은 집합이므로 false를 반환한다.
false 의미:
입력이 잘못됨
아님
false 의미:
새로운 컴포넌트 병합이 없었음업무 계층이 중복 link를 오류로 볼지는 별도 정책이라 체크해야한다.
메모리는 O(N)이다
32-bit parent와 size 배열 두 개는 원소당 8 bytes의 raw storage를 사용하는 걸 확인했다.
N = 10,000,000
raw arrays:
80,000,000 bytes
= 76.2939453125 MiB
≈ 76.3 MiBPython의 object list는 같은 논리 구조라도 훨씬 큰 overhead를 가질 수 있었다.(실제 측정결과) 그리고 일전에서 본 것처럼 문자열 ID 맵은 이 raw storage보다 한 자릿수 이상 클 수 있다. 대규모 입력에서는 언어별 실제 메모리를 측정해야 한다.
실패에 관련한 기록:
- 원소끼리 직접 parent를 연결해 cycle을 만듦
- Union 전에 root를 찾지 않음
- Root를 영구적인 business ID로 저장함
- 일반 node의 size slot을 직접 읽음
- Edge 삭제를 union의 반대 연산으로 처리함
- 외부 64-bit ID를 배열 index로 그대로 사용함
- 동시 find가 read-only라고 가정함
- Rollback DSU에 path halving을 포함한 경로 단축을 사용함
- 중복 union 때 componentCount를 감소시킴
- 실제 경로를 얻기 위해 parent forest를 graph path로 해석함
- 크기 검증 전에 배열을 먼저 할당함
- 문자열 index의 수명을 아무도 소유하지 않음6. 잘못된 예제
class DisjointSetBad
{
readonly #parent: number[];
public constructor(size: number)
{
this.#parent =
Array.from(
{ length: size },
(value, index) => index,
);
}
public connect(
left: number,
right: number,
): void
{
this.#parent[right] = left;
}
public find(node: number): number
{
if (this.#parent[node] === node) {
return node;
}
return this.find(
this.#parent[node],
);
}
}다음 호출을 살표보면 다음과 같다.
connect(0, 1)
parent[1] = 0
connect(1, 2)
parent[2] = 1
connect(2, 0)
parent[0] = 2결과:
0 → 2 → 1 → 0Parent forest가 아니라 cycle이 만들어진다. find(0)은 종료되지 않았다(처음 공부해서 작성했던 예제)
구체적인 문제점들:
- left와 right의 root를 찾지 않는다.
- 이미 연결된 집합인지 검사하지 않는다.
- union-by-size 또는 rank가 없다.
- path halving을 포함한 경로 단축이 없다.
- 재귀 호출이 긴 chain에서 stack을 소비한다.
- index 범위 검증이 없다.
- 컴포넌트 크기와 개수를 추적할 수 없다.
- cycle이 발생해도 감지하지 않는다.union은 두 임의 node를 연결하는 함수가 아니다.
잘못된 의미:
right의 parent를 left로 설정
올바른 의미:
right가 속한 집합의 root와
left가 속한 집합의 root를 병합7. 프로덕션으로 사용하기
Union-Find는 작은 예제에서는 맞아 보이지만, root 변경과 path halving 때문에 경계 오류가 숨어 있기 쉽다. Reference graph의 BFS 결과와 무작위 연산을 비교하는 상태 기반 테스트가 효과적이다.(이는 일반적 경험에서 나오는 당연한 논리적 귀결이다) Reference graph의 BFS 결과와 무작위 연산을 비교하는 상태 기반 테스트가 효과적이다.
TypeScript 결정적 무작위 테스트
import assert from "node:assert/strict";
import test from "node:test";
import {
DisjointSet,
type Result,
} from "./ds.ts";
test("Union-Find는 기준 graph 연결성과 같다", () =>
{
const nodeCount = 128;
for (const seed of [0x5eed, 0x1, 0xdeadbeef]) {
const created = DisjointSet.create(nodeCount);
assert.ok(created.ok);
if (!created.ok) {
assert.fail(JSON.stringify(created.error));
}
const sets = created.value;
const graph = createEmptyGraph(nodeCount);
const touched = new Set<number>();
const random = createDeterministicRandom(seed);
for (
let step = 0;
step < 20_000;
step += 1
) {
const left = randomIndex(random, nodeCount);
const right = randomIndex(random, nodeCount);
touched.add(left);
touched.add(right);
const expectedMerged =
!isConnectedByGraph(graph, left, right);
const actualMerged = sets.connect(left, right);
assert.ok(actualMerged.ok);
if (!actualMerged.ok) {
assert.fail(JSON.stringify(actualMerged.error));
}
addUndirectedEdge(graph, left, right);
assert.equal(actualMerged.value, expectedMerged);
verifyRandomQueries(
sets,
graph,
random,
nodeCount,
);
}
assert.equal(touched.size, nodeCount);
}
});
test("chain, star, balanced 병합 순서에서도 component 크기를 보존한다", () =>
{
const scenarios: readonly {
readonly name: string;
readonly edges: readonly (
readonly [number, number]
)[];
}[] = [
{
name: "chain",
edges: [
[0, 1], [1, 2], [2, 3], [3, 4],
[4, 5], [5, 6], [6, 7],
],
},
{
name: "star",
edges: [
[0, 1], [0, 2], [0, 3], [0, 4],
[0, 5], [0, 6], [0, 7],
],
},
{
name: "balanced",
edges: [
[0, 1], [2, 3], [4, 5], [6, 7],
[0, 2], [4, 6], [0, 4],
],
},
];
for (const scenario of scenarios) {
const created = DisjointSet.create(8);
assert.ok(created.ok, scenario.name);
if (!created.ok) {
assert.fail(JSON.stringify(created.error));
}
const sets = created.value;
for (const [left, right] of scenario.edges) {
assert.equal(
requireSuccess(sets.connect(left, right)),
true,
scenario.name,
);
}
assert.equal(
sets.getComponentCount(),
1,
scenario.name,
);
for (let node = 0; node < 8; node += 1) {
assert.equal(
requireSuccess(sets.getComponentSize(node)),
8,
scenario.name,
);
}
}
});
test("중복 union은 component 수를 줄이지 않는다", () =>
{
const created = DisjointSet.create(4);
assert.ok(created.ok);
if (!created.ok) {
assert.fail(JSON.stringify(created.error));
}
const sets = created.value;
const firstMerge = sets.connect(0, 1);
assert.ok(firstMerge.ok);
if (!firstMerge.ok) {
assert.fail(JSON.stringify(firstMerge.error));
}
assert.equal(
firstMerge.value,
true,
);
assert.equal(
sets.getComponentCount(),
3,
);
const repeatedMerge = sets.connect(1, 0);
assert.ok(repeatedMerge.ok);
if (!repeatedMerge.ok) {
assert.fail(JSON.stringify(repeatedMerge.error));
}
assert.equal(repeatedMerge.value, false);
assert.equal(
sets.getComponentCount(),
3,
);
});
test("컴포넌트 크기는 실제 원소 수와 같다", () =>
{
const created = DisjointSet.create(6);
assert.ok(created.ok);
if (!created.ok) {
assert.fail(JSON.stringify(created.error));
}
const sets = created.value;
for (const [left, right] of [
[0, 1],
[1, 2],
[3, 4],
[2, 4],
]) {
const merged = sets.connect(left, right);
assert.ok(merged.ok);
}
for (const node of [0, 1, 2, 3, 4]) {
const size = sets.getComponentSize(node);
assert.ok(size.ok);
if (!size.ok) {
assert.fail(JSON.stringify(size.error));
}
assert.equal(size.value, 5);
}
const isolatedSize = sets.getComponentSize(5);
assert.ok(isolatedSize.ok);
if (!isolatedSize.ok) {
assert.fail(JSON.stringify(isolatedSize.error));
}
assert.equal(isolatedSize.value, 1);
});
test("범위를 벗어난 입력은 Result 오류다", () =>
{
const created = DisjointSet.create(4);
assert.ok(created.ok);
if (!created.ok) {
assert.fail(JSON.stringify(created.error));
}
assert.deepEqual(
created.value.areConnected(0, 4),
{ ok: false, error: {
code: "invalid-node",
value: 4,
} },
);
assert.deepEqual(
created.value.areConnected(-1, 0),
{ ok: false, error: {
code: "invalid-node",
value: -1,
} },
);
assert.deepEqual(
created.value.getComponentSize(1.5),
{ ok: false, error: {
code: "invalid-node",
value: 1.5,
} },
);
assert.deepEqual(
DisjointSet.create(0),
{ ok: false, error: {
code: "invalid-element-count",
value: 0,
} },
);
assert.deepEqual(
DisjointSet.create(10_000_001),
{ ok: false, error: {
code: "invalid-element-count",
value: 10_000_001,
} },
);
});
type ReferenceGraph =
readonly Set<number>[];
function createEmptyGraph(
nodeCount: number,
): ReferenceGraph
{
return Array.from(
{ length: nodeCount },
() => new Set<number>(),
);
}
function requireAdjacency(
graph: ReferenceGraph,
node: number,
): Set<number>
{
const adjacency = graph[node];
if (adjacency === undefined) {
assert.fail("reference graph node is out of range.");
}
return adjacency;
}
function addUndirectedEdge(
graph: ReferenceGraph,
left: number,
right: number,
): void
{
requireAdjacency(graph, left)
.add(right);
requireAdjacency(graph, right)
.add(left);
}
function isConnectedByGraph(
graph: ReferenceGraph,
start: number,
target: number,
): boolean
{
if (start === target) {
return true;
}
const visited =
new Set<number>([start]);
const queue = [start];
for (
let index = 0;
index < queue.length;
index += 1
) {
const current = queue[index];
assert.ok(current !== undefined);
for (
const next of requireAdjacency(
graph,
current,
)
) {
if (next === target) {
return true;
}
if (!visited.has(next)) {
visited.add(next);
queue.push(next);
}
}
}
return false;
}
function verifyRandomQueries(
sets: DisjointSet,
graph: ReferenceGraph,
random: () => number,
nodeCount: number,
): void
{
for (let query = 0; query < 8; query += 1) {
const left =
randomIndex(random, nodeCount);
const right =
randomIndex(random, nodeCount);
assert.equal(
requireSuccess(
sets.areConnected(left, right),
),
isConnectedByGraph(
graph,
left,
right,
),
);
}
}
function requireSuccess<T>(
result: Result<T>,
): T
{
if (!result.ok) {
assert.fail(JSON.stringify(result.error));
}
return result.value;
}
function randomIndex(
random: () => number,
nodeCount: number,
): number
{
return Math.floor(
(random() / 0x1_0000_0000) * nodeCount,
);
}
function createDeterministicRandom(
seed: number,
): () => number
{
let state = seed >>> 0;
return () =>
{
state = (
Math.imul(state, 1_664_525)
+ 1_013_904_223
) >>> 0;
return state;
};
}실제 실행 결과
LCG seed 0x5eed, 0x1, 0xdeadbeef 각각에 대해 node 128개, union 20,000회, 매 union 뒤 연결성 질의 8회로 실행했다.
각 seed의 질의는 160,000회다. 아래 수치는 seed 0x5eed의 관측값이다.
실제 병합: 127회
이미 연결된 no-op: 19,873회
선택된 서로 다른 node: 128개
최종 component 수: 1개
node 0의 component 크기: 128개127 = 128 - 1이므로 모든 node가 하나의 component가 되는 데 필요한 실제 병합 수와 일치한다.
매 union과 질의 결과는 reference graph의 BFS 결과와 같았다. C# Release 실행도 같은 입력에서 같은 값을 낸 것을 체크했다.
PASS: C# Result contract, 127 merges, 19873 no-ops, 128/128 indices.invalid-node는 음수와 상한 이상 node에서, invalid-element-count는 0과 10,000,001에서 반환되는 것을 C#과 TypeScript에서 확인했다. Python 구현도 0, True, 범위 밖 node를 Failure(...)로 반환하는 것을 실행으로 확인했다.
ConnectivityIndex 경계도 실행했다. server a, b, c와 link a-b, b-c를 적재하면 areConnected("a", "c")는 success(true)를 반환했다. a가 두 번 들어간 snapshot은 duplicated-server-id, a-missing link는 unknown-server-id, 이미 취소된 signal은 aborted 오류를 반환했다. snapshot 읽기나 link stream이 취소 예외를 던지거나, 읽기 완료 직전에 signal이 취소된 경우도 aborted로 변환되는 것을 확인했다.
테스트에서 문제가 되는 지점.
random() % nodeCount로 index를 만들면 이 LCG의 하위 비트만 사용한다. 위 harness는 한 step에서 난수를 정확히 18번 소비한다.
left, right 두 번과 verifyRandomQueries()의 8회 X 2번이다. 매 step의 같은 argument position만 따로 보면 18 stride 때문에 state % 128은 64개 residue만 방문한다. 그러나 step 안의 18개 position 전체를 합치면 128개 node가 모두 선택될 수 있다.
하위 비트를 그대로 쓰는 더 직접적인 문제는 pair 구조다. 이 LCG는 multiplier와 increment가 모두 홀수라 하위 1비트가 매 호출마다 반전하는데, 연속한 두 출력을 left와 right로 쓰면 항상 서로 다른 parity가 짝이 된다.
같은 parity의 pair와 self-pair가 생성되지 않는다. randomIndex()는 상위 비트를 스케일링해 이 하위 비트 주기 문제를 피한다고 보아야 할 것이다. nodeCount가 2의 거듭제곱이 아닌 경우에도 분포가 완전히 균등하다고 주장하기보다, 직접적인 하위 비트 주기 결함을 제거한다고 설명하는 편이 정확하다.
requireAdjacency()와 assert.ok(current !== undefined)는 --noUncheckedIndexedAccess를 켠 프로젝트에서도 이 테스트 파일이 그대로 통과하게 만든다. undefined를 다른 노드로 바꾸지 않고 즉시 테스트를 실패시키므로 참조 구현의 결함이 있음을 명시적으로 확인 할 수 있다.
프로그래머는 언제나 명시적으로 적어놔야 나중에 봐도 안 헷갈린다.
핵심 불변식:
초기 상태:
componentCount == N
실제 병합:
componentCount는 정확히 1 감소
중복 병합:
componentCount는 변하지 않음
모든 node:
areConnected(node, node) == true
같은 컴포넌트의 모든 node:
getComponentSize(node)가 동일
모든 union 이후:
Reference BFS 연결성과 동일
빈 snapshot:
getComponentCount() == 0이고 조회는 Result 오류성능 측정 기준
비교 대상:
1. 매 질의마다 BFS·DFS
2. Union-Find without optimization
3. Union-by-size만 적용
4. Union-by-size + path halving측정 변수:
- 원소 수 N
- Union과 Query 비율
- 중복 edge 비율
- 입력 순서
- 컴포넌트 크기 분포
- 외부 ID mapping 비용
- 메모리 사용량Union-Find 자체가 빨라도 문자열 ID를 매번 hash하는 비용이 더 클 수 있다. 전체 호출 경계를 함께 측정해야 한다.
8. C++ / Python / C# / TypeScript 비교 메모
언어 | Parent 저장 | Size 저장 | 주요 위험 |
|---|---|---|---|
C++ |
|
| 멤버 선언 순서와 동시 경로 단축의 data race |
Python |
|
|
|
C# |
|
|
|
TypeScript |
|
| 외부 문자열 ID 변환 비용과 index의 수명 |
- 언어
C++
- Parent 저장
vector<uint32_t>- Size 저장
vector<uint32_t>- 주요 위험
멤버 선언 순서와 동시 경로 단축의 data race
- 언어
Python
- Parent 저장
list[int]- Size 저장
list[int]- 주요 위험
bool이int의 하위 타입, 객체 overhead와 interpreter loop
- 언어
C#
- Parent 저장
int[]- Size 저장
int[]- 주요 위험
AreConnected()와GetComponentSize()가 내부적으로 mutation함
- 언어
TypeScript
- Parent 저장
Int32Array- Size 저장
Int32Array- 주요 위험
외부 문자열 ID 변환 비용과 index의 수명
C++
조밀한 primitive vector 두 개라 locality가 좋고 소유권이 명확하다. findRoot()가 parent를 수정하므로 공유 읽기에도 synchronization이 필요하다.
uint32_t를 사용했기 때문에 최대 원소 수를 명확히 제한했다. 무조건 size_t를 사용하면 64-bit 환경에서 parent 배열의 메모리가 두 배가 될 수 있으므로 실제 최대 규모에 맞춰 index width를 선택한다.
멤버 초기화가 선언 순서를 따른다는 점은 이 언어에서만 나오는 함정이다. 2장의 생성자를 그대로 쓰면서 멤버 선언만 재배치하면 조용히 정의되지 않은 동작이 된다.
Python
알고리즘은 같지만 list[int]는 packed 32-bit 정수 배열이 아니다. 각 list slot과 integer object의 표현 비용이 존재한다.
수백만 원소가 병목이라면 다음을 검토할 수 있다.
- array("I")
- NumPy array
- Cython
- native extension그러나 Python loop가 hot path라면 저장 표현만 바꿔서는 충분하지 않을 수 있다.
C#
int[] 두 개는 compact하고 GC가 각 원소를 별도 객체로 추적하지 않는다. 원소 1000만 개면 배열 하나가 40 MB이므로 large object heap에 들어간다. 대형 배열은 managed heap 정책과 snapshot lifetime을 함께 고려해야 한다.
AreConnected()와 GetComponentSize()가 이름상 read operation처럼 보이지만 path halving으로 배열을 수정한다. API 문서나 별도 read-only snapshot 타입으로 이 사실을 드러내는 편이 API 설계에 핵심일 것이다.
TypeScript
Int32Array는 parent와 size를 고정 폭으로 저장한다. 일반 number[]보다 의도가 명확하며 sparse hole도 만들지 않는다.
여기서 Uint32Array를 쓸 수도 있다. node index와 component size는 본질적으로 음수가 될 수 없으므로 저장 표현만 보면 그쪽이 더 가깝다. 상한이 1000만이라 Int32Array의 약 21억 범위로도 충분하고, 두 배열의 element width가 같아 메모리도 같다.
다만 Uint32Array는 TypeScript의 음수 대입을 타입 수준에서 막지 못한다고 보인다.(테스트로 확인했음.)
element 타입은 여전히 number이고, values[0] = -1은 허용된 뒤 ToUint32 변환을 거쳐 4_294_967_295로 저장된다. 따라서 unsigned 배열을 써도 #nodeError() 같은 경계 검증은 필요하는 걸로 보인다Int32Array와 Uint32Array의 선택은 저장 표현과 감시(sentinel) 정책의 문제다.
다만 실제 서비스에서는 다음 비용이 더 클 수 있다.
serverId string
→ Map lookup
→ dense node index
→ Union-Find operationQuery가 많다면 호출자가 string을 반복 전달하지 않도록 검증된 NodeId handle을 상위 세션 안에서 캐시할 수 있다라고 보인다.
공통 계약
결국 이 구현에 대해서 공통적으로 구현해야하는 지점이다.
공통 계약:
- 원소 ID 범위
- 초기 컴포넌트 정의
- union-by-size 규칙
- 경로 단축 방식 (compression, splitting, halving 중 무엇인지)
- 중복 union 반환 의미
- root 비공개 정책
- edge 삭제 정책
- 동시성 소유권
- 검증과 할당의 순서9. 추가로 생각해보기
Edge 삭제가 하루에 한 번 발생한다면 동적 연결성 구조보다 전체 재구축이 더 단순하고 빠르지 않은가?
Root를 외부에 노출하지 않으면서 컴포넌트별 업무 metadata를 어떻게 안정적으로 연결할 것인가?
병렬 ingestion에서 하나의 concurrent DSU와 worker별 local DSU 후 병합 중 어느 구조가 실제 workload에 적합한가?
Rollback이 필요할 때 path compression을 포기하고 어떤 변경 이력을 stack에 저장할 것인가?
외부 ID가 문자열일 때 Map lookup 비용이 Union-Find 연산 비용보다 커지지는 않는가?
실제 연결 경로도 필요하다면 Union-Find와 adjacency graph를 함께 유지할 메모리 비용을 감수할 것인가?
문자열 index가 자료구조 본체보다 큰 측정 결과가 나왔다면, 이 인덱스를 누가 소유하고 언제 버리는가?
Result오류 코드를 호출부의 HTTP, CLI, 작업 큐 응답으로 어떻게 변환할 것인가?
10. 요약
Union-Find는 edge가 추가되는 graph의 연결 컴포넌트를 효율적으로 추적한다.
union은 임의 원소가 아니라 두 원소의 root를 병합해야 한다.Union-by-size는 작은 트리를 큰 트리에 붙이고, path halving은 반복 조회 경로를 줄인다. 이 조합은 역 Ackermann 계열의 상각 상한을 가진다.
Root와 root의 size는 내부 구현 정보이며 안정적인 업무 ID가 아니다.
areConnected()와getComponentSize()는 이름과 달리 쓰기 연산이다.Edge 삭제, 실제 경로 조회, 동시 수정은 기본 Union-Find의 책임 범위를 벗어난다.
크기 검증은 배열 할당보다 먼저 일어나야 하고, C++에서는 그 순서가 멤버 선언 순서에 달려 있다.
실제 메모리를 지배하는 것은 정수 배열이 아니라 외부 ID 맵일 수 있다.
정확성은 reference graph의 BFS 결과와 무작위 연산을 비교해 검증할 수 있다.
원소를 직접 연결하지 마라.
각 원소의 root를 찾고,
작은 컴포넌트의 root만
큰 컴포넌트의 root 아래에 붙여라.개인적인 메모: 핵심은 빠른 알고리즘과 객체 할당(Allocation) 모델을 따로 보지 않고 함께 설계하는 것이다. 알고리즘을 교체하더라도 입력 검증, 실패 계약, 상태의 소유권, 호출 경계가 유지된다면 바깥 구조는 대체로 남고 재활용 할 수 있다. 달라지는 것은 내부 자료구조와 성능 특성이다. 즉 실패 계약과 상태 소유권 정도가 프로그래머의 스타일 문제라고 할 수 있다.
각주
- Robert E. Tarjan, "Efficiency of a Good But Not Linear Set Union Algorithm" (1975), JACM 22(2), 215-225 ↩
- Robert E. Tarjan and Jan van Leeuwen, "Worst-case Analysis of Set Union Algorithms" (1984), JACM 31(2), 245-281 ↩
- GCC 14.2 manual, `-Wreorder` ↩
- Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup, "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity" (2001), JACM 48(4), 723-760 ↩
- Siddhartha V. Jayanti and Robert E. Tarjan, "A Randomized Concurrent Algorithm for Disjoint Set Union" (2016), PODC 2016, 75-82 ↩