PEP 372 – collections에 순서가 있는 딕셔너리 추가

Author:: Armin Ronacher <armin.ronacher at active-4.com>, Raymond Hettinger <python at rcn.com>
Status:: Final
Type:: Standards Track
Created:: 15-Jun-2008
Python-Version:: 2.7, 3.1
Post-History:

Table of Contents

초록
패치
근거
순서 있는 딕셔너리 API
질문과 답변
참조 구현
향후 방향
참고 자료
Copyright

번역·라이선스 안내

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

초록

이 PEP에서는 collections 모듈의 새로운 데이터 구조로 순서가 있는 딕셔너리를 제안하며, 이 PEP에서는 이를 “OrderedDict”라고 부릅니다. 제안된 API에는 다양한 실제 애플리케이션과 다른 프로그래밍 언어에 존재하는 유사한 구현을 다루면서 얻은 경험이 반영되어 있습니다.

패치

테스트와 문서를 포함한 작동하는 Py3.1 패치는 다음 위치에 있습니다:

OrderedDict patch

반영된 리비전은 70101과 70102입니다.

근거

현재 Python 버전에서 널리 사용되는 내장 dict 타입은 저장된 키/값 쌍의 순서를 지정하지 않습니다. 이 때문에 일부 특정 사용 사례에서 딕셔너리를 데이터 저장소로 사용하기가 어렵습니다.

PHP와 Ruby 1.9 같은 일부 동적 프로그래밍 언어는 반복 시 일정한 순서를 보장합니다. 이러한 언어와 기존 Python 순서 있는 딕셔너리 구현에서는 항목의 순서가 키를 삽입한 시점에 따라 정의됩니다. 새 키는 끝에 추가되지만, 덮어쓴 키는 끝으로 이동하지 않습니다.

다음 예제는 단순한 할당에서의 동작을 보여줍니다:

>>> d = OrderedDict()
>>> d['parrot'] = 'dead'
>>> d['penguin'] = 'exploded'
>>> d.items()
[('parrot', 'dead'), ('penguin', 'exploded')]

순서가 보존된다는 점은 OrderedDict를 몇 가지 상황에서 유용하게 만듭니다:

XML/HTML 처리 라이브러리는 현재 특성의 순서를 버리거나, 필터링을 번거롭게 만드는 dict 대신 리스트를 사용하거나, 자체 순서 있는 딕셔너리를 구현합니다. 이는 ElementTree, html5lib, Genshi 및 그 밖의 여러 라이브러리에 영향을 줍니다.
다양한 라이브러리와 애플리케이션에 순서 있는 딕셔너리 구현이 많이 있으며, 대부분은 서로 미묘하게 호환되지 않습니다. 게다가 dict를 서브클래싱하는 작업은 간단하지 않으며, 많은 구현이 모든 메서드를 올바르게 재정의하지 않아 예기치 않은 결과를 초래할 수 있습니다.
또한 많은 순서 있는 딕셔너리가 비효율적인 방식으로 구현되어, 여러 연산이 필요 이상으로 복잡해집니다.
PEP 3115에서는 메타클래스가 클래스 본문에 사용되는 매핑 객체를 변경할 수 있도록 허용합니다. 순서 있는 딕셔너리를 사용하여 C 구조체와 유사한 순서 있는 멤버 선언을 만들 수 있습니다. 이는 예를 들어 향후 ctypes 릴리스와, Django 프레임워크가 제공하는 것처럼 데이터베이스 테이블을 클래스로 정의하는 ORM에 유용할 수 있습니다. Django는 현재 데이터베이스 모델에서 멤버의 순서를 복원하기 위해 보기 좋지 않은 해킹을 사용합니다.
RawConfigParser 클래스는 애플리케이션이 내부에서 사용할 딕셔너리의 타입을 설정할 수 있도록 하는 dict_type 인자를 허용합니다. 이 추가의 동기는 사용자가 순서 있는 딕셔너리를 제공할 수 있도록 하기 위한 것이었습니다. [1]
PHP와 같은 다른 프로그래밍 언어에서 포팅된 코드는 순서 있는 딕셔너리에 의존하는 경우가 많습니다. 표준 라이브러리에 순서를 보존하는 딕셔너리 구현이 있으면 전환이 쉬워지고 서로 다른 라이브러리의 호환성이 향상될 수 있습니다.

순서 있는 딕셔너리 API

순서 있는 딕셔너리 API는 dict 및 기존 순서 있는 딕셔너리와 대부분 호환됩니다. 참고: 이 PEP는 collections.매핑 추상 베이스 클래스에 설명된 2.7 및 3.0 딕셔너리 API를 참조합니다.

생성자와 update()모두 dict와 같은 매핑뿐만 아니라 튜플의 이터러블도 허용합니다. 일반 딕셔너리와 달리 삽입 순서가 보존됩니다.

>>> d = OrderedDict([('a', 'b'), ('c', 'd')])
>>> d.update({'foo': 'bar'})
>>> d
collections.OrderedDict([('a', 'b'), ('c', 'd'), ('foo', 'bar')])

순서가 있는 딕셔너리를 일반 딕셔너리에서 업데이트하는 경우 새 키의 순서는 물론 정의되지 않습니다.

모든 이터레이션 메서드와 keys(), values()및 items()는 키가 처음 삽입된 시점에 따른 순서로 값을 반환합니다:

>>> d['spam'] = 'eggs'
>>> d.keys()
['a', 'c', 'foo', 'spam']
>>> d.values()
['b', 'd', 'bar', 'eggs']
>>> d.items()
[('a', 'b'), ('c', 'd'), ('foo', 'bar'), ('spam', 'eggs')]

dict에서 사용할 수 없는 새 메서드:

OrderedDict.__reversed__(): 키에 따른 역방향 이터레이션을 지원합니다.

질문과 답변

기존 키를 재할당하면 어떻게 됩니까?

키는 이동되지 않고 제자리에서 새 값이 할당됩니다. 이는 기존 구현과 일치합니다.

생성자에 전달된 목록에 키가 여러 번 나타나면 어떻게 됩니까?

일반 dict의 경우와 같습니다. 즉, 뒤의 항목이 앞의 항목을 덮어씁니다. 실제로 덮어쓰이는 것은 값뿐이므로 첫 번째 키의 위치가 사용되는 부작용이 있습니다:
>>> OrderedDict([('a', 1), ('b', 2), ('a', 3)])
collections.OrderedDict([('a', 3), ('b', 2)])
이 동작은 Python의 기존 구현, PHP 배열 및 Ruby 1.9의 해시맵과 일치합니다.

순서가 있는 딕셔너리는 dict 서브클래스입니까? 그 이유는 무엇입니까?

예. defaultdict와 마찬가지로 순서가 있는 딕셔너리는 dict를 서브클래싱합니다. dict 서브클래스이면 일부 메서드(예: __getitem__및 __len__)가 더 빨라집니다. 더 중요한 점은 dict 서브클래스이므로 순서가 있는 딕셔너리를 isinstance(d, dict)로 검사하여 dict 입력을 요구하는 json과 같은 도구에서 사용할 수 있다는 것입니다.

dict를 서브클래싱하면 어떤 제한이 발생합니까?

예. Py2.x와 Py3.x에서 dict의 API가 서로 다르므로 OrderedDict의 API도 서로 달라야 합니다. 따라서 Py2.7 버전에서는 iterkeys, itervalues 및 iteritems를 재정의해야 합니다.

OrderedDict.popitem()은 특정 키/값 쌍을 반환합니까?

예. 가장 최근에 삽입된 새 키와 그에 대응하는 값을 꺼냅니다. 이는 전통적인 push/pop 쌍에서 나타나는 일반적인 LIFO 동작에 해당합니다. 의미상 k=list(od)[-1]; v=od[k]; del od[k]; return (k,v)와 동일합니다. 실제 구현은 더 효율적이며 정렬된 키 목록에서 직접 꺼냅니다.

OrderedDict는 인덱싱, 슬라이싱 등을 지원합니까?

사실 OrderedDict는 Sequence 인터페이스를 구현하지 않습니다. 오히려 키 삽입 순서를 기억하는 MutableMapping입니다. 시퀀스와 유사하게 추가된 유일한 기능은 reversed 지원입니다.
인덱싱을 허용하지 않는 또 다른 장점은 연결 리스트를 사용하는 빠른 C 구현의 가능성을 열어 둔다는 점입니다.

OrderedDict는 알파벳순과 같은 다른 정렬 순서를 지원합니까?

아닙니다. 다른 정렬 순서를 원하는 경우에는 실제로 다른 기법을 사용해야 합니다. OrderedDict의 핵심은 삽입 순서를 기록하는 것입니다. 다른 순서가 중요하다면, 메모리 내 dbm과 같은 다른 구조가 더 적합할 가능성이 높습니다.

OrderedDict는 json 모듈, PyYAML 및 ConfigParser와 얼마나 잘 작동합니까?

json의 경우 좋은 소식은 json 인코더가 OrderedDict의 반복 순서를 존중한다는 점입니다.:
>>> items = [('one', 1), ('two', 2), ('three',3), ('four',4), ('five',5)]
>>> json.dumps(OrderedDict(items))
'{"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}'
Py2.6에서는 json 디코더의 object_hook에 이미 생성된 딕셔너리가 전달되므로, object hook이 이를 보기 전에 순서가 손실됩니다. 순서를 보존하는 새 훅을 추가하여 Python 2.7/3.1에서 이 문제가 수정되고 있습니다(https://github.com/python/cpython/issues/49631 참조). 새 훅을 사용하면 순서를 보존할 수 있습니다.:
>>> jtext = '{"one": 1, "two": 2, "three": 3, "four": 4, "five": 5}'
>>> json.loads(jtext, object_pairs_hook=OrderedDict)
OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})
PyYAML의 경우 전체 왕복 처리가 문제없이 가능합니다.:
>>> ytext = yaml.dump(OrderedDict(items))
>>> print ytext
!!python/object/apply:collections.OrderedDict
- - [one, 1]
  - [two, 2]
  - [three, 3]
  - [four, 4]
  - [five, 5]

>>> yaml.load(ytext)
OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5})
ConfigParser 모듈의 경우에도 왕복 처리가 문제없이 가능합니다. 정렬된 딕셔너리를 지원하기 위해 Py2.6에 사용자 정의 딕셔너리가 특별히 추가되었습니다.:
>>> config = ConfigParser(dict_type=OrderedDict)
>>> config.read('myconfig.ini')
>>> config.remove_option('Log', 'error')
>>> config.write(open('myconfig.ini', 'w'))

OrderedDict는 동등성 테스트를 어떻게 처리합니까?

두 정렬된 딕셔너리를 비교하면 테스트가 순서에 민감해져서 list(od1.items())==list(od2.items())가 됩니다.
정렬된 딕셔너리를 다른 매핑과 비교할 때는 순서에 무관한 비교가 사용됩니다. 따라서 일반 딕셔너리를 사용할 수 있는 모든 곳에서 정렬된 딕셔너리로 대체할 수 있습니다.

repr/eval 왕복 과정에서 __repr__ 형식은 순서를 어떻게 유지합니까?

OrderedDict([(‘a’, 1), (‘b’, 2)])

가능한 기반 데이터 구조의 장단점은 무엇입니까?

키의 정렬된 목록을 유지하면 __delitem__()을 제외한 모든 연산이 빠르며, __delitem__()은 O(n) 작업이 됩니다. 이 데이터 구조를 사용하면 코드가 매우 단순해지고 낭비되는 공간도 적습니다.

삽입 순서 번호를 기록하기 위해 별도의 딕셔너리를 유지하면 코드가 조금 더 복잡해집니다. 모든 기본 연산은 O(1)이지만 __setitem__() 및 __delitem__()의 상수 계수가 증가하므로, 모든 사용 사례가 이 속도 향상에 대한 비용을 부담해야 합니다(__setitem__()을 통해 모든 구축 작업이 진행되기 때문입니다). 또한 첫 번째 순회에서는 한 번만 발생하는 O(n log n) 정렬 비용이 발생합니다. 저장 공간 비용은 정렬된 키 목록 접근법의 두 배입니다.

C로 작성된 버전에서는 연결 리스트를 사용할 수 있습니다. 코드는 다른 두 접근법보다 복잡해지지만 공간을 절약하고 일반 딕셔너리와 동일한 빅오 성능을 유지할 수 있습니다. 이 방식이 가장 빠르고 공간 효율적입니다.

참조 구현

테스트와 문서가 포함된 구현은 다음 위치에 있습니다:

OrderedDict patch

제안된 버전에는 여러 장점이 있습니다:

MutableMapping API를 엄격히 준수하고 새로운 메서드가 없어 학습 곡선이 거의 없습니다. 단순히 삽입 순서를 기억하는 딕셔너리입니다.
일반적으로 좋은 성능을 보입니다. 빅오 시간은 키 삭제가 O(n)이라는 점을 제외하면 일반 딕셔너리와 동일합니다.

여기서 제안하는 API에 영감을 준, 다양한 파이썬 프로젝트나 독립 라이브러리에 있는 순서가 있는 딕셔너리의 다른 구현들은 다음과 같습니다: