PEP 603 – collections에 frozenmap 타입 추가

Author:: Yury Selivanov <yury at edgedb.com>
Discussions-To:: Discourse thread
Status:: Draft
Type:: Standards Track
Created:: 12-Sep-2019
Post-History:: 12-Sep-2019

Table of Contents

번역·라이선스 안내

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

초록

영속 데이터 구조는 데이터가 수정될 때 데이터의 이전 버전을 보존하는 데이터 구조로 정의됩니다. 이러한 데이터 구조는 사실상 불변입니다. 이러한 구조에 대한 연산은 구조를 제자리에서 업데이트하지 않고, 대신 항상 새로 업데이트된 구조를 생성하기 때문입니다(자세한 내용은 [0] 참조).

이 PEP는 collections 모듈에 frozenmap이라는 완전히 영속적이고 불변인 새로운 매핑 타입을 추가할 것을 제안합니다.

frozenmap의 참조 구현 대부분은 이미 CPython에서 contextvars 모듈을 구현하는 데 사용되고 있습니다.

근거

Python에는 불변 컬렉션 타입이 두 가지 있습니다. tuple과 frozenset입니다. 이러한 타입은 불변 리스트와 집합을 나타내는 데 사용할 수 있습니다. 그러나 불변 매핑을 나타내는 방법은 아직 존재하지 않으며, 이 PEP는 불변 매핑을 구현하기 위해 frozenmap을 제안합니다.

제안된 frozenmap 타입은 다음을 지원합니다:

collections.abc.Mapping프로토콜을 구현합니다.
피클링을 지원합니다.
“수정된” 버전을 효율적으로 생성하기 위한 API를 제공합니다.

다음 사용 사례는 불변 매핑이 바람직한 이유를 보여 줍니다.

불변 매핑은 해시 가능하므로 딕셔너리 키나 집합 요소로 사용할 수 있습니다.
이러한 해시 가능 특성 덕분에 @functools.lru_cache()로 데코레이터가 적용된 함수가 불변 매핑을 인자로 받을 수 있습니다. 불변 매핑과 달리, 이러한 함수에 일반 dict를 전달하면 오류가 발생합니다.
불변 매핑은 복잡한 상태를 저장할 수 있습니다. 불변 매핑은 참조로 복사할 수 있으므로 상태의 트랜잭션 변이를 효율적으로 구현할 수 있습니다.
불변 매핑은 스레드와 비동기 작업의 경계를 넘어 딕셔너리를 안전하게 공유하는 데 사용할 수 있습니다. 불변성은 스레드와 비동기 작업을 더 쉽게 추론할 수 있게 합니다.

마지막으로 CPython [1]에는 frozenmap 구현에 필요한 C 코드의 주요 부분이 이미 포함되어 있습니다. contextvars 모듈을 구현하기 위한 C 코드는 이미 존재합니다(자세한 내용은 PEP 567를 참조하십시오). 이 C 코드를 공개 컬렉션 타입을 통해 노출하면 해당 코드의 사용자가 크게 증가합니다. 이는 버그를 발견하고 성능을 개선하여 코드 품질 향상으로 이어집니다. frozenmap 컬렉션이 없다면 대부분의 프로그램이 contextvars 모듈을 간접적으로 사용하기 때문에 이러한 개선은 매우 어려웠을 것입니다.

사양

collections 모듈에 새로운 공개 불변 타입인 frozenmap이 추가됩니다.

생성

frozenmap은 dict와 유사한 생성 API를 구현합니다.

frozenmap()은 비어 있는 새로운 불변 매핑을 생성합니다.
frozenmap(**kwargs)는 **kwargs에서 매핑을 생성합니다. 예를 들면 frozenmap(x=10, y=0, z=-1)과 같습니다.
frozenmap(collection)은 전달된 collection 객체로부터 매핑을 생성합니다. 전달된 collection 객체는 다음 중 하나일 수 있습니다:
- dict입니다.
- 또 다른 frozenmap입니다.
- items() 메서드를 가지며 키/값 튜플 시퀀스를 반환할 것으로 예상되는 객체입니다.
- 키/값 튜플의 이터러블입니다.

데이터 액세스

frozenmap은 collection.abc.Mapping프로토콜을 구현합니다. 따라서 getter, 멤버십 검사 및 반복은 dict와 동일한 방식으로 작동합니다.:

m = frozenmap(foo='bar')

assert m['foo'] == 'bar'
assert m.get('foo') == 'bar'
assert 'foo' in m

assert 'baz' not in m
assert m.get('baz', 'missing') == 'missing'

assert m == m
assert m != frozenmap()  # m is not equal to an empty frozenmap

assert len(m) == 1

# etc.

변경

frozenmap 인스턴스는 불변입니다. 그렇지만 불변 인스턴스의 변경된 복사본을 효율적으로 생성할 수 있습니다.

변경 작업의 복잡도는 O(log N)이며, 구조적 공유를 사용하므로 결과로 생성되는 frozenmap 복사본은 추가 메모리를 거의 사용하지 않는 경우가 많습니다(자세한 내용은 [6]을 읽으십시오.)

frozenmap.including(key, value)

이 메서드는 새로운 키 / 값 쌍이 포함된 새로운 frozenmap 복사본을 생성합니다.:

m = frozenmap(foo=1)
m2 = m.including('bar', 100)

print(m)   # will print frozenmap({'foo': 1})
print(m2)  # will print frozenmap({'foo': 1, 'bar': 100})

frozenmap.excluding(key)

이 메서드는 삭제된 키를 포함하지 않는 frozenmap의 복사본을 생성합니다.:

m = frozenmap(foo=1, bar=100)

m2 = m.excluding('foo')

print(m)   # will print frozenmap({'foo': 1, 'bar': 100})
print(m2)  # will print frozenmap({'bar': 1})

m3 = m.excluding('spam')  # will throw a KeyError('spam')

frozenmap.union(매핑=None, **kw)

이 메서드는 frozenmap의 복사본을 생성하고, 생성된 복사본에 여러 키/값을 추가하거나 수정합니다. 이 메서드의 시그니처는 frozenmap 생성자의 시그니처와 일치합니다.:

m = frozenmap(foo=1)

m2 = m.union({'spam': 'ham'})
print(m2)  # will print frozenmap({'foo': 1, 'spam': 'ham'})

m3 = m.union(foo=100, y=2)
print(m3)  # will print frozenmap({'foo': 100, 'y': 2})

print(m)   # will print frozenmap({'foo': 1})

N개의 키를 추가하거나 대체할 때 union() 메서드를 호출하는 것이 including() 메서드를 N번 호출하는 것보다 효율적입니다.

frozenmap.mutating()

이 메서드를 사용하면 여러 변경 사항이 적용된 frozenmap 인스턴스의 복사본을 효율적으로 생성할 수 있습니다. 이 메서드는 해당 frozenmap에 수천 개의 키/값 쌍이 포함되어 있고 성능이 중요한 코드 구역에서 그중 많은 항목을 업데이트해야 할 때 특히 유용합니다.

frozenmap.mutating() 메서드는 frozenmap 객체의 변경 가능한 딕셔너리형 복사본인 collections.FrozenMapCopy 인스턴스를 반환합니다.

FrozenMapCopy 객체는 다음과 같습니다:

해당 객체가 생성된 frozenmap 인스턴스 데이터의 copy-on-write 뷰입니다.
변경 가능하지만, 해당 객체에 대한 변경은 객체가 생성된 frozenmap 인스턴스에 영향을 주지 않습니다.
frozenmap 생성자에 전달할 수 있으며, FrozenMapCopy 객체에서 frozenmap을 생성하는 작업은 O(1)입니다.
가져오기/설정 작업의 복잡도는 O(log N)이며, 객체를 생성하는 작업은 O(1)입니다.
데이터에 대한 추가 액세스나 변경을 방지하는 FrozenMapCopy.close() 메서드를 가집니다.
컨텍스트 관리자로 사용할 수 있습니다.

mutating()를 컨텍스트 관리자와 함께 사용할 수 있음을 아래 예제가 보여 줍니다.:

numbers = frozenmap((i, i ** 2) for i in range(1_000_000))

with numbers.mutating() as copy:
    for i in numbers:
        if not (numbers[i] % 997):
            del copy[i]

    numbers_without_997_multiples = frozenmap(copy)

    # at this point, *numbers* still has 1_000_000 key/values, and
    # *numbers_without_997_multiples* is a copy of *numbers* without
    # values that are multiples of 997.

    for i in numbers:
        if not (numbers[i] % 593):
            del copy[i]

    numbers_without_593_multiples = frozenmap(copy)

    print(copy[10])  # will print 100.

print(copy[10])  # This will throw a ValueError as *copy*
                 # has been closed when the "with" block
                 # was executed.

반복

frozenmap이 표준 collections.abc.Mapping프로토콜을 구현하므로, 반복에 필요한 모든 메서드가 지원됩니다.:

assert list(m) == ['foo']
assert list(m.items()) == [('foo', 'bar')]
assert list(m.keys()) == ['foo']
assert list(m.values()) == ['bar']

dict와 달리 frozenmap에서의 반복은 삽입 순서를 보존하지 않습니다.

해싱

frozenmap 인스턴스는 tuple 객체와 마찬가지로 해시 가능할 수 있습니다.:

hash(frozenmap(foo='bar'))  # works
hash(frozenmap(foo=[]))     # will throw an error

타입 지정

frozenmap에 표준 타이핑 표기법을 사용할 수 있습니다.:

m: frozenmap[str, int] = frozenmap()

구현

제안된 frozenmap 불변 타입은 해시 배열 매핑 트라이(Hash Array Mapped Trie, HAMT) 데이터 구조를 사용합니다. Clojure와 같은 함수형 프로그래밍 언어는 불변 해시 테이블, 벡터 및 집합을 효율적으로 구현하기 위해 HAMT를 사용합니다.

HAMT

HAMT의 핵심 설계 계약은 key의 해시가 주어졌을 때 예측 가능한 value를 보장하는 것입니다. key와 value의 쌍에 대해 key의 해시를 사용하여 해시 맵 트리에서 value의 위치를 결정할 수 있습니다.

HAMT로 구현된 불변 매핑은 set()및 get()연산에 대해 O(log N)의 성능을 가집니다. 이러한 효율성은 변경 연산이 트리의 한 분기에만 영향을 주기 때문에 가능하며, 따라서 변경되지 않은 분기를 재사용하고 수정되지 않은 데이터를 복사하지 않을 수 있습니다.

HAMT에 대한 자세한 내용은 [5]에서 확인하십시오. CPython 구현 [1]에도 알고리즘에 대한 상당히 자세한 설명이 있습니다.

성능

../_images/pep-0603-hamt_vs_dict.png — Figure 1. Benchmark code can be found here: [3].

위 차트는 다음을 보여 줍니다.

HAMT로 구현된 frozenmap은 벤치마크 대상인 모든 딕셔너리 크기에서 O(1)에 가까운 성능을 보입니다.
약 100~200개의 항목을 사용하면 dict.copy()의 효율성이 떨어집니다.

../_images/pep-0603-lookup_hamt.png — Figure 2. Benchmark code can be found here: [4].

그림 2는 dict와 HAMT 기반 불변 매핑의 조회 비용을 비교합니다. HAMT 조회 시간은 평균적으로 파이썬 딕셔너리 조회보다 약 30% 느립니다. 이러한 성능 차이는 얕은 트리를 순회하는 것이 평평하고 연속적인 배열에서 조회하는 것보다 비효율적이기 때문에 발생합니다.

[6]을 인용하면 다음과 같습니다. “[using HAMT]는 실제로 영속 해시 배열 매핑 트라이에 대한 삽입, 삭제 및 조회가 계산 복잡도 O(log n)을 가지지만, 어떤 연산이든 12단계를 넘기려면 극히 많은 수의 항목이 필요하므로 대부분의 애플리케이션에서는 사실상 일정한 시간이라는 의미입니다.”

설계 고려 사항

“FrozenMap”이 아니라 “frozenmap”인 이유

소문자 “frozenmap”은 frozenset 내장 타입뿐만 아니라 collections.defaultdict와 같은 타입과도 잘 어울립니다.

“frozendict”가 아니라 “frozenmap”인 이유

“Dict”는 Python에서 매우 구체적인 의미를 가집니다.

dict는 O(1)의 get 및 set 연산을 제공하는 abc.MutableMapping의 구체적인 구현입니다(frozenmap의 복잡도는 O(log N)입니다).
Python 딕셔너리는 삽입 순서를 보존합니다.

제안된 frozenmap은 앞서 언급한 속성들을 가지고 있지 않습니다. 대신 frozenmap은 O(log N)의 설정/조회 연산 비용을 가지며, abc.Mapping 프로토콜만 구현합니다.

Python 개선 제안 한국어 번역