PEP 218 – 내장 집합 객체 타입 추가하기

Author:: Greg Wilson <gvwilson at ddj.com>, Raymond Hettinger <python at rcn.com>
Status:: Final
Type:: Standards Track
Created:: 31-Jul-2000
Python-Version:: 2.2
Post-History:

Table of Contents

소개
근거
제안
집합 표기법
역사
가변성
Copyright

번역·라이선스 안내

이 비공식 한국어 번역은 원문 Copyright 절의 Public Domain 조건에 따라 제공합니다. 원저자와 공식 원문은 그대로 표시합니다. 수정되지 않은 기준 원문 · 공식 최신판

소개

이 PEP는 Python 표준 라이브러리에 Set 모듈을 추가하고, 그 모듈이 널리 쓰이게 되면 집합을 Python 내장 타입으로 만들 것을 제안합니다. 집합이 왜 바람직한지, 그리고 집합 대신 딕셔너리를 사용하는 흔한 관용구가 왜 부적절한지 설명한 뒤, 내장 집합이 어떻게 동작하도록 할 것인지, 그리고 예비 Set 모듈이 어떻게 동작할 것인지 기술합니다. 마지막 절에서는 집합과 집합 원소의 가변성(또는 불변성)을 논의하고, Set 모듈이 구현할 해법을 다룹니다.

근거

집합은 기본적인 수학적 구조이며, 알고리즘 명세에서 매우 흔히 사용됩니다. 그러나 구현에서는 집합이 “올바른” 구조인 경우에도 훨씬 드물게 사용됩니다. 프로그래머들은 리스트의 순서 정보가 무의미하고 값에 의한 조회가 빈번한 경우에도 리스트를 대신 사용하는 일이 많습니다. (대부분의 중간 규모 C 프로그램에는 특정 항목이 존재하는지 확인하려고 malloc으로 할당한 벡터를 처음부터 끝까지 탐색하는 코드가 우울할 만큼 많이 들어 있습니다…)

프로그래머들은 집합을 “상관없는” 값을 가진 딕셔너리로 구현할 수 있다는 말을 자주 듣습니다. 이러한 “집합”에는 항목에 “상관없는” 값을 대입하여 항목을 추가할 수 있고, dict.has_key를 사용하여 멤버십을 검사할 수 있으며, del을 사용하여 항목을 삭제할 수 있습니다. 그러나 집합의 다른 주요 연산(합집합, 교집합, 차집합)은 이 표현 방식에서 직접 지원되지 않습니다. 키/값 쌍을 담은 딕셔너리에서는 이러한 연산의 의미가 모호하기 때문입니다.

제안

이 PEP의 장기적인 목표는 Python에 내장 집합 타입을 추가하는 것입니다. 딕셔너리가 키/값 쌍의 순서 없는 컬렉션인 것처럼, 이 타입은 고유한 값의 순서 없는 컬렉션이 될 것입니다.

반복과 컴프리헨션은 자명한 방식으로 구현되므로,:

for x in S:

위 코드는 S의 원소를 임의의 순서로 차례차례 순회하며,:

set(x**2 for x in S)

위 코드는 S의 모든 원소의 제곱을 담은 집합을 만들어 냅니다. 멤버십은 in과 not in을 사용하여 검사하며, 기본 집합 연산은 오버로드된 연산자와 메서드를 함께 사용하여 구현합니다. 연산자는 다음과 같습니다:

`\|`	합집합
`&`	교집합
`^`	대칭 차집합
`-`	비대칭 차집합
`== !=`	동등 및 부등 검사
`< <= >= >`	부분집합 및 상위집합 검사

메서드는 다음과 같습니다:

`S.add(x)`	집합에 “x”를 추가합니다.
`S.update(s)`	시퀀스 “s”의 모든 원소를 집합에 추가합니다.
`S.remove(x)`	집합에서 “x”를 제거합니다. “x”가 존재하지 않으면 이 메서드는 `LookupError` 예외를 발생시킵니다.
`S.discard(x)`	집합에 “x”가 있으면 제거하고, 없으면 아무것도 하지 않습니다.
`S.pop()`	임의의 원소를 제거하고 반환하며, 원소가 없으면 `LookupError`를 발생시킵니다.
`S.clear()`	이 집합의 모든 원소를 제거합니다.
`S.copy()`	새 집합을 만듭니다.
`s.issuperset()`	상위 집합 관계인지 검사합니다.
`s.issubset()`	부분 집합 관계인지 검사합니다.

그리고 두 개의 새로운 내장 변환 함수가 있습니다:

`set(x)`	컬렉션 “x”의 원소를 담은 집합을 만듭니다.
`frozenset(x)`	컬렉션 “x”의 원소를 담은 불변 집합을 만듭니다.

참고 사항:

교집합과 합집합에는 비트 연산자 “|&”를 사용할 것을 제안합니다. 합집합에 “+”를 쓰는 것은 직관적이지만, 교집합에 “*”를 쓰는 것은 그렇지 않습니다(질문을 받은 사람 중 그 동작을 올바르게 추측한 사람은 극소수였습니다).
집합에 원소를 추가할 때 “add” 대신 “+”를 사용하는 방안도 검토했습니다. 그러나 Guido van Rossum은 다른 내장 타입에서 “+”가 대칭적이라는 점을 지적했습니다(”*”는 그렇지 않지만). “add”를 사용하면 그 연산과 합집합 연산 사이의 혼동도 피할 수 있습니다.

집합 표기법

이 PEP는 원래 집합 표기법으로 {1,2,3}을, 공집합 표기법으로 {-}를 제안했습니다. Python 2.3의 sets.py를 사용해 본 경험에 따르면 이 표기법은 필요하지 않았습니다. 또한 딕셔너리를 한눈에 알아보기 어렵게 만들 위험도 다소 있었습니다.

중괄호 표기법이 집합 컴프리헨션을 지원하도록 하는 방안도 고려했습니다. 그러나 Python 2.4에서 도입된 제너레이터 표현식이 그 필요를 완전히 충족했으며, 더 일반적인 방식으로 이를 해결했습니다. (제너레이터 표현식에 관한 자세한 내용은 PEP 289를 참조하십시오.)

그래서 Guido는 집합 문법을 두지 않기로 결정했습니다. 다만 이 문제는 Python 3000에서 다시 검토될 수 있습니다(PEP 3000 참조).

역사

집합을 사용해 본 경험을 쌓기 위해 Python 2.3에서 순수 Python 모듈이 도입되었습니다. 그 구현을 바탕으로 Python 2.4에서 set 타입과 frozenset 타입이 도입되었습니다. 개선 사항은 다음과 같습니다:

frozenset을 위한 더 나은 해시 알고리즘
더 간결한 pickle 형식(값이 항상 True인 키:값 쌍의 딕셔너리 대신 원소 리스트만 저장합니다).
깊은 복사가 자동으로 이루어지도록 __reduce__ 함수를 사용합니다.
BaseSet 개념이 제거되었습니다.
union_update() 메서드는 그냥 update()가 되었습니다.
가변 집합과 불변 집합 사이의 자동 변환이 제거되었습니다.
_repr 메서드가 제거되었습니다(새로운 sorted() 내장 함수가 그 필요를 충족합니다).

Tim Peters는 클래스의 생성자가 단일 시퀀스를 인자로 받아 그 시퀀스의 원소들로 집합을 채워야 한다고 생각합니다. 그의 논거(인자)는 대부분의 경우 프로그래머가 기존 시퀀스로부터 집합을 만들 것이므로, 이 경우를 일반적인 경우로 삼아야 한다는 것입니다. 그러나 이렇게 하면 사용자는 이미 알고 있는 값으로 집합을 초기화할 때 괄호 한 쌍을 추가로 기억해야 합니다:

>>> Set((1, 2, 3, 4))       # case 1

반면에 소수의 Python 초보 사용자(모두 다른 언어에는 매우 숙련된 사람들이었습니다)에게서 받은 피드백에 따르면 사람들은 “괄호 없는” 문법을 더 자연스럽게 여길 것입니다:

>>> Set(1, 2, 3, 4)         # case 2

결국 우리는 초기화 메서드가 단일 이터러블 인자를 받는 첫 번째 전략을 채택했습니다.

가변성

이 제안에서 해결하기 가장 어려웠던 문제는 집합이 가변 원소를 포함할 수 있어야 하는지 여부였습니다. 딕셔너리의 키는 빠르고 신뢰할 수 있는 조회를 지원하기 위해 불변이어야 합니다. 집합 원소가 불변이어야 한다고 요구하기는 쉽겠지만, 그렇게 하면 집합의 집합(그래프 알고리즘과 기타 응용에서 널리 사용됩니다)을 만들 수 없게 됩니다.

PEP 218의 초기 초안에는 집합 타입이 하나뿐이었지만, Python 2.3의 sets.py 구현에는 Set과 ImmutableSet 두 가지가 있습니다. Python 2.4에서는 새로운 내장 타입의 이름을 조금 덜 번거로운 set과 frozenset으로 정했습니다.

“sets” 모듈에는 두 개의 클래스가 구현되어 있습니다. Set 클래스의 인스턴스는 원소를 추가하거나 제거하여 수정할 수 있으며, ImmutableSet 클래스는 변경할 수 없는 원소 모음을 가진 “동결된” 클래스입니다. 따라서 ImmutableSet은 딕셔너리 키나 집합 원소로 사용할 수 있지만, 갱신할 수는 없습니다. 두 집합 타입 모두 원소가 불변이며 해시 가능한 객체여야 합니다. “set” 및 “frozenset” 내장 타입에도 같은 설명이 적용됩니다.

Copyright

This document has been placed in the Public Domain.