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

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 2.4에서 set과 frozenset 타입이 도입되었습니다. 개선 사항은 다음과 같습니다:

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

Tim Peters는 클래스의 생성자가 단일 시퀀스를 인자로 받아, 그 시퀀스의 요소들로 세트를 채워야 한다고 믿습니다. 그의 주장은, 대부분의 경우 프로그래머들이 이미 존재하는 시퀀스로부터 세트를 만들 것이므로, 이 경우가 일반적인 경우가 되어야 한다는 것입니다. 하지만 이는 알려진 값들로 세트를 초기화할 때 사용자가 괄호를 추가로 하나 더 기억해야 하는 문제를 야기합니다:

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

반면, (모두 다른 언어에 매우 능숙한) 소수의 파이썬 초보 사용자들로부터 받은 피드백에 따르면, 사람들은 “괄호 없는” 문법을 더 자연스럽게 느낄 것이라고 합니다:

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

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

가변성

이 제안에서 해결하기 가장 어려운 질문은 집합(set)이 가변 요소를 포함할 수 있어야 하는지 여부였습니다. 딕셔너리의 키는 빠르고 신뢰할 수 있는 조회를 지원하기 위해 불변이어야 합니다. 집합 요소를 불변으로 요구하는 것은 쉽겠지만, 이는 (그래프 알고리즘 및 기타 응용에서 널리 사용되는) 집합의 집합을 배제하게 됩니다.

초기 PEP 218 초안에는 세트 타입이 하나뿐이었지만, Python 2.3의 sets.py 구현에는 Set과 ImmutableSet 두 가지가 있습니다. Python 2.4에서는 새로운 내장 타입들이 다소 덜 번거로운 set과 frozenset으로 명명되었습니다.

“sets” 모듈에는 두 클래스가 구현되어 있습니다. Set 클래스의 인스턴스는 요소의 추가나 제거로 수정될 수 있으며, ImmutableSet 클래스는 요소의 컬렉션이 변경 불가능하게 “고정(frozen)”되어 있습니다. 따라서 ImmutableSet은 딕셔너리 키나 집합 요소로 사용될 수 있지만 갱신될 수는 없습니다. 두 종류의 집합 모두 요소가 불변이고 해시 가능한 객체일 것을 요구합니다. “set”과 “frozenset” 내장 타입에도 동일한 설명이 적용됩니다.

Copyright

This document has been placed in the Public Domain.