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 패치

체크인은 리비전 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.Mapping 추상 베이스 클래스에 기술된 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를 서브클래싱하면 어떤 제약이 생깁니까?

그렇습니다. dict의 API는 Py2.x와 Py3.x에서 서로 다르므로, 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은 이미 만들어진 딕셔너리를 전달하므로, 객체 훅이 딕셔너리를 받기 전에 이미 순서가 사라집니다. 이 문제는 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 패치

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

MutableMapping API를 엄격하게 준수하고 새로운 메서드가 없으므로 학습 부담이 거의 없습니다. 단순히 삽입 순서를 기억하는 딕셔너리일 뿐입니다.
전반적으로 성능이 좋습니다. 키 삭제가 O(n)이라는 점을 제외하면 빅오 시간 복잡도는 일반 딕셔너리와 같습니다.

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