집합 (추상 자료형)

3. 타입 이론

타입 이론에서 집합은 일반적으로 해당 지표 함수(특성 함수)와 동일시된다. 따라서 $A$ 타입의 값 집합은 $2^\{A\}$ 또는 $\backslash mathcal\{P\}(A)$로 표기될 수 있다. (하위 타입 및 부분 집합은 세분화 타입으로 모델링될 수 있으며, 몫 집합은 집합체로 대체될 수 있다.) 집합 $S$의 특성 함수 $F$는 다음과 같이 정의된다.^[1]

:$F(x)\; =\; \backslash begin\{cases\}$

1, & \mbox{if } x \in S \\

0, & \mbox{if } x \not \in S

\end{cases}

4. 구현

집합은 다양한 자료 구조를 사용하여 구현할 수 있으며, 이는 다양한 연산에 대해 서로 다른 시간과 공간의 트레이드오프를 제공한다. 일부 구현은 `nearest` 또는 `union`과 같은 매우 특수한 연산의 효율성을 개선하도록 설계되었다. "일반 용도"로 설명된 구현은 일반적으로 `element_of`, `add` 및 `delete` 연산을 최적화하려고 한다. 간단한 구현 방법은 리스트를 사용하여 요소의 순서를 무시하고 중복된 값을 피하는 것이다. 이는 간단하지만 비효율적인데, 집합 멤버십 또는 요소 삭제와 같은 연산은 전체 리스트를 스캔해야 하므로 ''O''(''n'')이기 때문이다. 집합은 대신 더욱 효율적인 자료 구조, 특히 다양한 종류의 트리, 트라이, 또는 해시 테이블을 사용하여 구현되는 경우가 많다.

집합은 지표 함수를 통해 일종의 맵으로 해석될 수 있으므로, 각 키-값 쌍의 값이 단위형 또는 센티넬 값(예: 1)인 (부분) 맵(연관 배열)과 동일한 방식으로 집합이 일반적으로 구현된다. 즉, 정렬된 집합의 경우 자체 균형 이진 탐색 트리 (대부분의 연산에 대해 O(log n)이 소요됨), 정렬되지 않은 집합의 경우 해시 테이블 (대부분의 연산에 대해 평균적으로 O(1)이지만 최악의 경우 O(n)이 소요됨)을 사용한다. 정렬된 선형 해시 테이블^[8]은 결정적으로 정렬된 집합을 제공하는 데 사용될 수 있다.

또한 맵은 지원하지만 집합은 지원하지 않는 언어에서 맵을 사용하여 집합을 구현할 수 있다.

다른 인기 있는 방법으로는 배열이 있다. 특히 정수 1..''n''의 부분 집합은 ''n'' 비트의 비트 배열로 효율적으로 구현할 수 있으며, 이는 매우 효율적인 합집합 및 교집합 연산도 지원한다. 블룸 맵은 매우 콤팩트한 표현을 사용하여 집합을 확률적으로 구현하지만 쿼리에 대해 작은 오탐 가능성을 감수한다.

부울 집합 연산은 더 기본적인 연산(pop, clear 및 add)으로 구현할 수 있지만, 특수 알고리즘은 더 낮은 점근적 시간 경계를 생성할 수 있다. 예를 들어, 집합이 정렬된 리스트로 구현된 경우 union(''S'',''T'')에 대한 단순한 알고리즘은 ''S''의 길이 ''m''과 ''T''의 길이 ''n''에 비례하는 시간이 걸린다. 반면, 리스트 병합 알고리즘의 변형은 ''m''+''n''에 비례하는 시간에 작업을 수행한다. 또한 다른 연산을 희생하여 이러한 연산 중 하나 이상에 최적화된 특수 집합 자료 구조(예: 합집합-찾기 자료 구조)가 있다.

5. 프로그래밍 언어 지원

• 파스칼은 집합을 지원하는 초기 언어 중 하나였으며, 현재 많은 언어가 핵심 언어 또는 표준 라이브러리에 집합을 포함하고 있다.
• C++의 표준 템플릿 라이브러리(STL)는 `set` 템플릿 클래스를 제공하며, 이는 일반적으로 레드-블랙 트리와 같은 이진 검색 트리를 사용하여 구현된다. SGI의 STL은 해시 테이블을 사용하는 `hash_set` 템플릿 클래스도 제공한다. C++11은 해시 테이블을 사용하는 `unordered_set` 템플릿 클래스를 지원한다. 집합의 요소는 키 역할을 하며, (상대적 또는 절대적) 위치를 사용하여 액세스되는 시퀀스 컨테이너와는 다르다. 집합 요소는 엄격한 약한 순서를 가져야 한다.
• 러스트 표준 라이브러리는 제네릭 [https://doc.rust-lang.org/std/collections/struct.HashSet.html HashSet] 및 [https://doc.rust-lang.org/std/collections/struct.BTreeSet.html BTreeSet] 유형을 제공한다.
• 자바는 인터페이스를 제공하여 집합을 지원하며 ( `HashSet` 클래스는 해시 테이블을 사용하여 구현), `SortedSet` 하위 인터페이스는 정렬된 집합을 지원한다 (`TreeSet` 클래스는 이진 검색 트리를 사용하여 구현).
• 애플의 파운데이션 프레임워크(코코아의 일부)는 Objective-C 클래스 [https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/ NSSet], [https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/ NSMutableSet], [https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSCountedSet_Class/ NSCountedSet], [https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSOrderedSet_Class/Reference/Reference.html NSOrderedSet] 및 [https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSMutableOrderedSet_Class/Reference/Reference.html NSMutableOrderedSet]을 제공한다. CoreFoundation API는 C에서 사용할 수 있는 [https://developer.apple.com/documentation/CoreFoundation/Reference/CFSetRef/ CFSet] 및 [https://developer.apple.com/documentation/CoreFoundation/Reference/CFMutableSetRef/ CFMutableSet] 유형을 제공한다.
• 파이썬은 2.4 이후부터 기본 제공 [https://docs.python.org/library/stdtypes.html#set-types-set-frozenset `set` 및 `frozenset` 유형]을 가지고 있으며, 파이썬 3.0 및 2.7 이후부터는 중괄호 구문(예: `{x, y, z}`)을 사용하여 비어 있지 않은 집합 리터럴을 지원한다. 빈 집합은 `set()`을 사용하여 생성해야 하는데, 이는 파이썬이 빈 딕셔너리를 나타내기 위해 `{}`를 사용하기 때문이다.
• .NET 프레임워크는 제네릭 [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet] 및 [http://msdn.microsoft.com/en-us/library/dd412070.aspx SortedSet] 클래스를 제공하며, 이들은 제네릭 [http://msdn.microsoft.com/en-us/library/dd412081.aspx ISet] 인터페이스를 구현한다.
• 스몰토크 클래스 라이브러리는 `Set` 및 `IdentitySet`을 포함하며, 각각 동등성 및 ID를 사용하여 포함 테스트를 수행한다. 많은 방언이 압축된 저장소(`NumberSet`, `CharacterSet`), 정렬(`OrderedSet`, `SortedSet` 등) 또는 약한 참조 (`WeakIdentitySet`)를 위한 변형을 제공한다.
• 루비 표준 라이브러리는 해시 테이블을 사용하여 집합을 구현하는 `Set` 및 `SortedSet` 클래스를 포함하는 [http://ruby-doc.org/stdlib/libdoc/set/rdoc/index.html set] 모듈을 포함하며, 후자는 정렬된 순서로 반복을 허용한다.
• OCaml 표준 라이브러리에는 이진 검색 트리를 사용하여 함수형 집합 데이터 구조를 구현하는 `Set` 모듈이 포함되어 있다.
• GHC의 하스켈 구현은 이진 검색 트리를 사용하여 불변 집합을 구현하는 `[https://hackage.haskell.org/package/containers/docs/Data-Set.html Data.Set]` 모듈을 제공한다.^[9]
• Tcl Tcllib 패키지는 TCL 목록을 기반으로 집합 데이터 구조를 구현하는 집합 모듈을 제공한다.
• 스위프트 표준 라이브러리에는 스위프트 1.2부터 `Set` 유형이 포함되어 있다.
• 자바스크립트는 ECMAScript 2015^[10] 표준을 통해 표준 내장 객체로 `[https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set Set]`을 도입했다.
• Erlang 표준 라이브러리에는 `[http://erlang.org/doc/man/sets.html sets]` 모듈이 있다.
• 클로저는 해시된 집합에 대한 리터럴 구문을 가지며 정렬된 집합도 구현한다.
• 랩뷰는 버전 2019부터 집합을 네이티브로 지원한다.
• 에이다는 `[http://www.ada-auth.org/standards/12rm/html/RM-A-18-8.html Ada.Containers.Hashed_Sets]` 및 `[http://www.ada-auth.org/standards/12rm/html/RM-A-18-9.html Ada.Containers.Ordered_Sets]` 패키지를 제공한다.

6. 중복 데이터 처리

데이터의 동일성은 주어진 비교 함수로 판단되므로, 외부 문맥에서 동일한지는 함수에 의존한다. 예를 들어 문자열 "hoge"와 "HOGE"는 다른 데이터로 볼 수도 있고, 대소문자를 구별하지 않고 비교하면 (항상 대문자화 또는 소문자화한 것끼리 비교하면) 동일한 데이터로 볼 수도 있다.

이러한 중복된 데이터를 삽입하려고 시도한 경우에는 다음처럼 처리할 수 있다.

• 무시한다.
• 새로운 것으로 교체한다.
• 다중화한다. (멀티셋 참조)

7. 다른 추상 자료형과의 차이점

• 리스트는 각 데이터에 순서가 정의된다는 점에서 집합과 다르다.
• 배열은 순서가 정의될 뿐만 아니라, 정적 배열의 경우 저장 가능한 요소 수도 변경할 수 없다는 점이 집합과 다르다.
• 멀티셋(bag이라고도 불림)은 같은 데이터를 여러 개 저장할 수 있지만, 좁은 의미의 집합에서는 중복된 데이터는 무시된다.

8. 멀티셋 (Multiset)

'''멀티셋'''(multiset) 또는 '''가방(bag)'''은 집합과 유사하지만, 집합과 달리 중복된("같은") 값을 허용하는 자료구조이다. 멀티셋은 같은 값을 단순히 세는 "동일한" 것으로 간주하거나, 같은 값을 "동등한" 것으로 간주하여 별개의 항목으로 저장하는 두 가지 방식으로 사용된다.

예를 들어, 사람 목록(이름별)과 나이(년 단위)가 주어졌을 때, 특정 연령의 사람 수를 단순히 세는 나이의 멀티셋을 구성할 수 있다. 또는, 나이가 같으면 두 사람이 동등하다고 간주되지만 다른 사람이고 다른 이름을 가질 수 있는 사람의 멀티셋을 구성할 수 있다. 이 경우 각 쌍(이름, 나이)을 저장해야 하며, 특정 나이를 선택하면 해당 나이의 모든 사람을 얻을 수 있다.

형식적으로, 컴퓨터 과학에서 객체는 어떤 동치 관계 하에서 "같다"고 간주될 수 있지만, 다른 관계 하에서는 여전히 별개로 간주될 수 있다. 일부 멀티셋 구현은 별개의 동일한 객체를 데이터 구조의 별도 항목으로 저장하는 반면, 다른 유형은 단일 버전(처음 발견된 것)으로 축소하고 요소의 개수를 양의 정수로 유지한다.

집합과 마찬가지로, 멀티셋은 해시 테이블이나 트리를 사용하여 구현할 수 있으며, 이는 서로 다른 성능 특성을 제공한다.

유형 T에 대한 모든 가방의 집합은 bag T 식으로 주어진다. 멀티셋을 동일한 항목을 동일하다고 간주하고 단순히 센다면, 멀티셋은 입력 도메인에서 음이 아닌 정수(자연수)로의 함수로 해석할 수 있으며, 이는 집합을 지표 함수로 식별하는 것을 일반화한다. 어떤 경우에는 이 계산 의미의 멀티셋이 파이썬에서와 같이 음수 값을 허용하도록 일반화될 수 있다.

여러 프로그래밍 언어에서 멀티셋을 지원하거나, 멀티셋을 지원하지 않는 경우에도 해결 방법이 존재한다.

가방에 대한 일반적인 연산은 다음과 같다.

• `contains(''B'', ''x'')`: 요소 ''x''가 가방 ''B''에 (적어도 한 번) 존재하는지 확인
• `is_sub_bag(''B''<sub>1</sub>, ''B''<sub>2</sub>)`: 가방 ''B''₁의 각 요소가 가방 ''B''₂에서 발생하는 빈도보다 더 자주 ''B''₁에서 발생하는지 확인. 때로는 ''B''₁ ⊑ ''B''₂로 표기한다.
• `count(''B'', ''x'')`: 요소 ''x''가 가방 ''B''에 발생하는 횟수를 반환한다. 때로는 ''B'' # ''x''로 표기한다.
• `scaled_by(''B'', ''n'')`: 자연수 ''n''이 주어지면, 가방 ''B''와 동일한 요소를 포함하는 가방을 반환하며, 가방 ''B''에서 ''m''번 발생하는 모든 요소가 결과 가방에서 ''n'' * ''m''번 발생하는 것을 제외한다. 때로는 ''n'' ⊗ ''B''로 표기한다.
• `union(''B''<sub>1</sub>, ''B''<sub>2</sub>)`: 가방 ''B''₁ 또는 가방 ''B''₂에서 발생하는 값만 포함하는 가방을 반환하지만, 결과 가방에서 값 ''x''가 발생하는 횟수는 (''B''₁ # x) + (''B''₂ # x)와 같다. 때로는 ''B''₁ ⊎ ''B''₂로 표기한다.

참조

_[1] 문서 pop() https://docs.python.[...] Python
_[2] 서적 Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings https://books.google[...]
_[3] 문서 Issue7212 http://bugs.python.o[...] Python
_[4] 문서 Feature #4553 https://bugs.ruby-la[...] Ruby
_[5] 서적 Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning https://books.google[...] Springer 2003-08-21
_[6] 서적 Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10 https://books.google[...]
_[7] 문서 flatten() http://www.ruby-doc.[...] Ruby
_[8] 간행물 Sorted Linear Hash Table http://www.concentri[...]
_[9] 뉴스 Efficient sets: a balancing act http://www.swiss.ai.[...] Journal of Functional Programming 1993-10
_[10] 웹사이트 ECMAScript 2015 Language Specification – ECMA-262 6th Edition http://www.ecma-inte[...] 2017-07-11
_[11] 문서 4. 組み込み型 — Python 3.6.5 ドキュメント https://docs.python.[...]
_[12] 문서 library set (Ruby 2.1.0) http://docs.ruby-lan[...]