[Python] 딕셔너리와 집합

References

Fluent Python

Dict Comprehension (dictcomp)
Mapping Methods
Other Mapping Types
Building Custome Mappings (UserDict)
Immutable Mappings
Dictionary views
Set
Hash Table, Index Collision

dict 타입은 여러 어플리케이션에서 널리 사용될 뿐만 아니라 파이썬의 핵심이기도 합니다. 모듈 네임스페이스, 클래스 및 인스턴스 속성, 함수의 키워드 인수 등 핵심 부분에서 딕셔너리(dictionary)가 사용되고 있습니다. build-in 함수는 모두 __buildints__.__dict__에 들어 있습니다.

이처럼 중요한 역할을 담당하고 있기 때문에 파이썬 dict 클래스는 상당하게 최적화되어 있습니다. 파이썬의 고성능 딕셔너리 뒤에는 Hash table(해시 테이블)이라는 엔진이 있습니다.

집합(Set)도 해시 테이블을 이용해서 구현하므로, 이번 포스팅에서는 딕셔너리와 집합에 대해서 살펴보겠습니다. 해시 테이블이 동작하는 방식을 알아야 딕셔너리와 집합을 최대로 활용할 수 있습니다.

Standard API of Mapping Types

collections.abc 모듈은 dict 및 이와 유사한 타입의 인터페이스를 정의하기 위해 Mapping 및 MutableMapping 추상 베이스 클래스(ABC)를 제공합니다.

추상 베이스 클래스는 매핑에 제공해야 하는 최소한의 인터페이스를 정의하고 문사화하기 위한 것이며, 넓은 의미의 매핑을 지원해야 하는 코드에서 isinstance() 테스트를 하기 위한 기준으로 사용됩니다.

함수 인수가 dict 타입인지 검사하는 것보다 isinstance() 함수를 사용하는 것이 좋은데, 다른 매핑 타입이 사용될 수 있기 때문입니다.

커스텀 매핑을 구현하기 위해서 추상 베이스 클래스를 상속하는 대신 collections.UserDict을 확장하거나 dict을 래핑하는 것이 더 쉽습니다. collections.UserDict 클래스와 표준 라이브러리의 모든 매핑 클래스는 이들 구현에서 기본 dict을 캡슐화하며 이는 해시 테이블에 구축되어 있습니다. 이는 표준 라이브러리에서 제공하는 매핑 타입이 모두 dict을 이용해서 구현하므로, 키가 hashable해야 한다는 제한을 가지고 있다는 것을 의미합니다. (값은 해시 가능할 필요가 없습니다.)

What is Hashable ?

파이썬(Glossary — Python 3.10.2 documentation)에서는 Hashable(해시 가능하다)이라는 용어를 다음과 같이 정의하고 있습니다.

lifetime 동안 결코 변하지 않는 해시값을 갖고 있고(__hash__() 메소드가 필요) 다른 객체와 비교할 수 있으면(__eq__() 메소드가 필요), 객체를 해시 가능하다고 합니다. 동일하다고 판단되는 객체는 반드시 해시값이 동일해야 합니다.

수치 타입과 flat 불변 타입인 str과 bytes는 모두 해시 가능합니다. 컨테이너의 경우에는 컨테이너가 불변하거나 포함하는 모든 객체 또한 모두 해시가 가능하다면, 그 컨테이너는 해시 가능합니다. frozenset은 언제나 해시 가능한데, 모든 요소가 해시 가능하도록 정의되어 있기 때문입니다. 튜플은 들어 있는 모든 항목이 모두 해시 가능해야 해시 가능합니다.

다음 코드에서 tt, tl, tf 튜플을 살펴보겠습니다.

사용자 정의 타입은 기본적으로 해시 가능합니다. 기본적으로 객체의 해시값은 id()를 이용해서 구하므로 모든 객체가 서로 다르기 때문입니다. 객체가 자신의 내부 상태를 평가해서 __eq__() 메소드를 직접 구현하는 경우에는 해시값 계산에 사용되는 속성이 모두 불변형일 때만 해시 가능합니다.

기본적인 규칙은 위와 같습니다. 이러한 규칙을 통해 다양한 방식으로 딕셔너리를 구현할 수 있는데, 공식 문서에는 다음과 같은 방법으로 딕셔너리를 구현하는 것을 보여줍니다.

a = dict(one=1, two=2, three=3)
b = {'one':1, 'two':2, 'three':3}
c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
d = dict([('two', 2), ('one', 1), ('three', 3)])
e = dict({'three':3, 'one':1, 'two':2})
print(a == b == c == d == e) # True

Dict Comprehensions

파이썬 2.7부터는 리스트 컴프리헨션(listcomp)과 제너레이터 표현식(genexps) 구문이 딕셔너리 컴프리헨션(dictionay comprehension=dictcomp)에도 적용됩니다 (이는 집합 컴프리헨션(set comprehension)도 마찬가지 입니다). dictcomp는 모든 반복가능한 객체에서 키-값 쌍을 생성함으로써 딕셔너리 객체를 만들 수 있습니다. 아래 예제 코드는 딕셔너리 컴프리헨션을 이용해서 동일한 튜플 리스트에서 딕셔너리 두 개를 생성하는 과정을 보여줍니다.

DIAL_CODES = [
    (82, 'Korea'),
    (91, 'India'),
    (1, 'United States'),
    (62, 'Indonesia'),
    (55, 'Brazil'),
    (92, 'Pakistan'),
    (880, 'Bangladesh'),
    (234, 'Nigeria'),
    (7, 'Russia'),
]
country_code = {country: code for code, country in DIAL_CODES}
print(country_code)

print({code: country.upper() for country, code in country_code.items()})

Overview of Common Mapping Methods

매핑에서 제공되는 기본 API는 아주 많습니다. 아래 표는 dict와 dict의 변형 중 가장 널리 사용되는 defaultdict과 OrderedDict 클래스가 구현하는 메소드를 보여줍니다. 너무 많기 때문에 기본 object 클래스에서 정의하는 메소드는 생략되어 있으며, 선택적 인수는 대괄호로 표시되었습니다.

	dict	defaultdict	OrderedDict
d.clear()	●	●	●	Remove all items
d.__contains__(k)	●	●	●	k in d
d.copy()	●	●	●	얕은 복사
d.__copy__()		●		Support for copy.copy
d.default_factory		●		빠진 값을 설정하기 위해 __missing__() 메소드에 호출되는 Callable
d.__delitem__(k)	●	●	●	del d[k] - 키가 k인 항목을 제거
d.fromkeys(it, [initial])	●	●	●	옵셔널 initial 값(기본 None)을 받아, 반복 가능한 객체의 키들을 이용해서 새로 매핑
d.get(k, [default])	●	●	●	키가 k인 항목을 반환, 만약 해당 항목이 없다면 default나 None을 반환
d.__getitem__(k)	●	●	●	d[k] - 키가 k인 항목을 반환
d.items()	●	●	●	(key, value) 쌍으로 구성된 항목들의 view를 가져온다
d.__iter__()	●	●	●	키에 대한 iterator를 가져온다
d.keys()	●	●	●	키에 대한 view를 가져온다
d.__len__()	●	●	●	len(d)
d.__missing__(k)		●		__getitem__()이 k 키를 찾을 수 없을 때 호출된다
d.move_to_end(k, [last])			●	앞이나 뒤에서 k 개의 항목을 이동. last의 기본값은 True)
d.pop(k, [default])	●	●	●	k 키 항목을 제거하고 반환. 해당 항목이 없다면 default나 None을 반환
d.popitem()	●	●	●	처음이나 마지막 (key, value) 항목을 제거하고 반환한다.
d.__reversed__()	●	●	●	키에 대한 역순 iterator를 가져온다
d.setdefault(k, [default])	●	●	●	k in d가 True라면 d[k]를 반환하고, False라면 d[k] = default로 설정하고 이 값을 반환한다
d.__setitem__(k, v)	●	●	●	d[k] = v
d.update(m, [**kargs])	●	●	●	(key, value) 쌍의 매핑이나 반복 가능한 객체에서 가져온 항목들로 d를 갱신
d.values()	●	●	●	value에 대한 view를 가져온다.

update() 메소드가 첫 번째 인수 m을 다루는 방식은 덕 타이핑(duck typing)의 대표적인 사례입니다. 먼저 m이 keys() 메소드를 갖고 있는지 확인한 후, 만약 메소드를 갖고 있으면 매핑이라고 간주합니다. keys() 메소드가 없으면, update() 메소드는 m의 항목들이 (key, value) 쌍으로 되어 있다고 간주하고 m을 반복합니다. 대부분의 파이썬 매핑은 update() 메소드와 같은 논리를 내부적으로 구현합니다. 따라서 매핑은 다른 매핑으로 초기화하거나, (key, value) 쌍을 생성할 수 있는 반복형 객체로 초기화할 수 있습니다.

매핑의 setdefault() 메소드는 늘 필요한 것은 아니지만 이 메소드가 필요할 때는 똑같은 키를 여러 번 조회하지 않게 해줌으로써 속도를 엄청나게 향상시킵니다.

Handling Missing Keys with setdefault()

파이썬의 fail-fast 철학에 따라, 존재하지 않는 키 k로 d[k]를 접근하면 dict는 에러를 발생시킵니다. KeyError를 처리하는 것보다 기본값을 사용하는 것이 더 편리한 경우에는 d[k] 대신 d.get(k, default)를 사용합니다. 그렇지만 발견한 값을 갱신할 때, 해당 객체가 가변 객체면 __getitem__()이나 get() 메소드는 보기 어색하고, 효율도 떨어집니다.

아래 예제 코드는 잘 짜여진 코드는 아니지만, 존재하지 않는 키를 처리할 때 dict.get()이 좋지 않은 사례라는 것을 보여줍니다.

여기서 사용되는 파일은 zen.txt를 참조해주세요.

"""Build an index mapping word -> list of occurrences"""
import sys
import re

WORD_RE = re.compile(r'\w+')

index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            # this is ugly; coded link this to make a point
            occurrences = index.get(word, []) # Get the list of occurrence sfor word, or [] if not found
            occurrences.append(location) # Append new location to occurences
            index[word] = occurrences # Put changed occurrences into index dict; 
                                      # this entails a second search through the index

# pinrt in alphabetical order
for word in sorted(index, key=str.upper):
    print(word, index[word])

위 코드를 작성하고 test.py로 저장한 뒤, 아래처럼 실행하면,

'$ python text.py ./zen.txt'

다음의 결과를 확인할 수 있습니다.

여기서 단어가 발생했을 때 처리하는 코드 3줄(line15 ~ 17)은 dict.setdefault()를 사용하면 한 줄로 바꿀 수 있습니다.

"""Build an index mapping word -> list of occurrences"""
import sys
import re

WORD_RE = re.compile(r'\w+')

index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            index.setdefault(word, []).append(location)

# pinrt in alphabetical order
for word in sorted(index, key=str.upper):
    print(word, index[word])

3줄에 걸쳐 작성된 코드는 line 14처럼 수정되었습니다.

my_dict.setdefault(key, []).append(new_value)

위 코드의 실형 결과는 다음 코드를 실행한 결과와 동일합니다.

if key not in my_dict:
    my_dict[key] = []
my_dict[key].append(new_value)

다만 이 코드는 키를 두 번 검색하는 반면(key가 없는 경우 3번), setdefault()를 사용한 코드는 단 한 번만 검색해서 이 모든 과정을 수행합니다.

Mappings with Flexible Key Lookup

검색할 때, 키가 존재하지 않는 경우 어떤 특별한 값을 반환하는 매핑이 있으면 편리할 때가 종종 있습니다. 이런 딕셔너리를 만드는 방법은 크게 2가지 입니다. 하나는 평범한 dict 대신 defaultdict를 사용하는 방법이고, 다른 하나는 dict 등의 매핑형을 상속해서 __missing__() 메소드를 추가하는 방법입니다.

defaultdict: Another Take on Missing Keys

아래의 예제 코드는 collections.defaultdict를 사용하여, 방금 위에서 살펴본 문제(나타나는 단어 검색)를 또 다른 방법으로 해결합니다. defaultdict는 존재하지 않는 키로 검색할 때 요청에 따라 항목을 생성하도록 설정되어 있습니다.

동작하는 방식은, defaultdict 객체를 생성할 때 존재하지 않는 key를 인수로 __getitem__() 메소드를 호출할 때마다 기본값을 생성하기 위해 사용되는 Callable을 제공하는 것입니다.

예를 들어, dd = defaultdict(list) 코드로 기본 defaultdict 객체를 생성한 후, dd에 존재하지 않는 키인 'new-key'로 dd['new-key'] 표현식을 실행하면 다음과 같이 처리됩니다.

리스트를 새로 생성하기 위해 list()를 호출
'new-key'를 키로 사용하여 새로운 리스트를 dd에 삽입
리스트에 대한 참조를 반환

이때, 기본값을 생성하는 Callable은 default_factory라는 객체 속성에 저장됩니다.

"""Build an index mapping word -> list of occurrences"""
import sys
import re
import collections

WORD_RE = re.compile(r'\w+')

index = collections.defaultdict(list) # Create a defaultdict with the list contructor as default_factory
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            index[word].append(location) # If word is not initially in the index, the default_factory is called
                                         # to produce the missing value, which in this case is an empty list that
                                         # is then assigned to index[word] and returned, so the .append(location)
                                         # operation always succeeds.

# pinrt in alphabetical order
for word in sorted(index, key=str.upper):
    print(word, index[word])

만약 default_factory가 설정되어 있지 않으면, 키가 없을 때 흔히 볼 수 있는 KeyError가 발생합니다.

실제 defaultdict가 default_factory를 호출하게 만드는 메커니즘은 __missing__() 스페셜 메소드에 읜존하며, 표준 매핑형은 모두 이 기능을 지원합니다.

missing() 메소드

매핑 타입은 __missing__() 메소드를 이용해서 존재하지 않는 키를 처리합니다. 이 스페셜 메소드는 기본 클래스인 dict에는 정의되어 있지 않지만, dict는 이 메소드를 알고 있습니다. 따라서 dict 클래스를 상속하고 __missing__() 메소드를 정의하면, dict.__getitem__() 표준 메소드가 키를 발견할 수 없을 때, KeyError를 발생시키지 않고 __missing__() 메소드를 호출합니다.

__missing__() 메소드는 d[k] 연산자를 사용하는 등, __getitem__() 메소드를 사용할 때만 호출됩니다. in 연산자를 구현하는 get()이나 __contains__() 메소드 등 키를 검색하는 다른 메소드에는 __missing__() 메소드가 영향을 미치지 않습니다. 따라서 __getitem__() 메소드를 사용할 때만 defaultdict의 default_factory가 동작합니다.

검색할 때 키를 str형으로 변환하는 매핑을 생각해보도록 하겠습니다. 다음 예제 코드는 키를 문자열로 변환하는 매핑이 어떻게 동작하는지 보여줍니다.

- 'd[key]'를 사용해서 항목을 가져오는 테스트

- 'd.get(key)'를 사용해서 항목을 가져오는 테스트

- 'in' 연산자 테스트

아래 코드는 위에서 사용한 StrKeyDict0 클래스를 구현합니다.

class StrKeyDict0(dict):
    def __missing__(self, key):
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]
    
    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return default
    
    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()

사용자 정의 매핑 타입을 만들 때는 dict보다 collections.UserDict 클래스를 상속하는 것이 더 낫습니다. 여기서는 dict.__getitem__() 내장 메소드가 __missing__() 메소드를 지원한다는 것을 보여주기 위해 dict 클래스를 상속합니다.

위 코드에서 __missing__() 메소드에 isinstance(key, str) 코드는 왜 필요한 것 일까요?

이렇게 검사하는 부분이 없다면, __missing__() 메소드는 k가 문자열이든 비문자열이든 str(k) 키가 존재할 때 문제없이 동작합니다. 하지만 str(k) 키가 존재하지 않으면 무한히 재귀적으로 호출됩니다. __missing__() 메소드에서 마지막 줄의 self[str(key)]가 str키를 이용해서 __getitem__() 메소드를 호출하고, 이때 키가 없으면 __missing__() 메소드를 다시 호출하기 때문입니다.

위 예제가 일관성 있게 동작하려면, __contains__() 메소드도 필요합니다. k in d 연산이 __contains__() 메소드를 호출하지만, dict에서 상속받은 __contains__() 메소드가 __missing__() 메소드를 호출하지 않기 때문입니다. 앞에서 구현한 __contains__() 메소드를 살펴보면, 키를 검색할 때 일반적인 스타일인 'k in my_dict'로 조회하지 않습니다. 'str(key) in self' 표현식을 사용하면 재귀적으로 __contains__() 메소드를 호출하기 때문인데, 이러한 문제를 피하기 위해서 여기서는 'key in self.keys()'와 같이 명시적으로 키를 조회합니다.

파이썬 3에서는 아주 큰 매핑에서도 'k in my_dict.keys()' 형태의 검색이 효율적입니다. dict.keys()는 집합과 비슷한 view를 반환하는데, 집합에 포함되었는지 여부를 검사하는 것은 딕셔너리만큼 빠르기 때문입니다.

앞서 나온 코드는 'key in self.keys()'를 이용해서 수정하지 않은 키에 대한 검사를 해야 제대로 동작합니다. StrKeyDict0은 딕셔너리에 들어 있는 키가 모두 str 타입이어야 한다고 요구하지 않기 때문입니다. 이 간단한 예제는 엄격하게 타입에 따르도록 하는 것이 아니라, 단순히 검색할 수 있게 해주는 방법을 보여주기 위한 것입니다.

Variations of dict

defaultdict 이외에 표준 라이브러리의 collections 모듈에서 제공하는 여러 매핑 타입을 간단하게 살펴보겠습니다.

collections.OrderedDict

키를 삽입한 순서대로 유지함으로써 항목을 반복하는 순서를 예측할 수 있습니다. OrderedDict의 popitem() 메소드는 기본적으로 최근에 삽입한 항목을 꺼내지만, my_odict.popitem(last=True) 형태로 호출하면 처음 삽입한 항목을 꺼냅니다.

collections.ChainMap

매핑들의 목록을 담고 있으며, 한꺼번에 모두 검색할 수 있도록 해줍니다. 각 매핑을 차례대로 검색하고, 그중 하나에서라도 키가 검색되면 성공합니다. 이 클래스는 내포된 범위를 지원하는 언어에서 각 범위를 하나의 매핑으로 표현함으로써 인터프리터를 구현하는 데 유용하게 사용될 수 있습니다. 파이썬 문서의 collections 절에서 'ChainMap 객체' 부분을 보면 ChainMap을 사용하는 여러 예제를 볼 수 있는데, 그중 아래 코드는 파이썬에서 변수를 조회하는 기본 규칙을 표현하고 있습니다.

import builtins
pylookup = ChainMap(locals(), globals(), vars(builtins))

collections.Counter

모든 키에 정수형 카운터를 갖고 있는 매핑 타입입니다. 기존 키를 갱신하면 카운터가 증가합니다. 이 카운터는 해시 가능한 객체(키)나 한 항목이 여러 번 들어갈 수 있는 다중 집합(multiset)에서 객체의 수를 세기 위해 사용할 수 있습니다. Counter 클래스는 함계를 구하기 위한 +와 - 연산자를 구현하며, 가장 많이 사용된 n개의 항목과 그들의 카운터로 구성된 튜플의 리스트를 반환하는 most_common([n]) 등의 메소드를 제공합니다. 자세한 내용은 공식 문서를 참조하시길 바랍니다.

다음 코드는 Counter를 이용해서 단어 안에서 각 글자의 횟수를 계산하는 예를 보여줍니다.

Subclassing UserDict (custome mappings)

dict보다 UserDict를 상속해서 매핑 타입을 만드는 것이 훨씬 쉽습니다. 매핑에 추가한 키를 문자열로 저장하기 위해서 위에서 StrKeyDict0을 확장했던 것처럼 UserDict의 값을 평가할 수 있습니다.

build-in 타입에서는 아무런 문제없이 상속할 수 있는 메소드들을 오버라이드해야 하는 구현의 특이성 때문에 dict보다는 UserDict를 상속하는 것이 낫습니다.

UserDict는 dict를 상속하지 않고 내부에 실제 항목을 담고 있는 data라고 하는 dict 객체를 갖고 있습니다. 이렇게 구현함으로써 __setitem__() 등의 스페셜 메소드를 구현할 때 발생하는 원치않는 재귀 호출을 피할 수 있으며, __contains__() 메소드를 간단히 구현할 수 있습니다.

UserDict로 구현한 StrKeyDict는 위에서 구현한 StrKeyDict0보다 간단하지만 더 많은 작업을 하도록 구현할 수 있습니다. StrKeyDict는 모든 키를 str타입으로 저장함으로써 비문자열 키로 객체를 생성하거나 갱신할 때 발생할 수 있는 예기치 못한 문제들을 피하게 해줍니다.

import collections

class StrKeyDict(collections.UserDict):
    def __missing__(self, key):
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]
    
    def __contains__(self, key):
        return str(key) in self.data
    
    def __setitem__(self, key, item):
        self.data[str(key)] = item

여기서 __contains__() 메소드는 더 간단해졌습니다. 저장된 키가 모두 str 타입이므로 StrKeyDict0에서 self.keys()를 호출하는 방법과 달리 self.data에서 바로 조회할 수 있습니다. 또한 __setitem__() 메소드는 모든 키를 str 타입으로 변환하므로, 연산을 self.data에 위임할 때 더 간단히 작성할 수 있습니다.

UserDict 클래스가 MutableMapping을 상속하므로 StrKeyDict는 결국 UserDict, MutableMapping, 또는 Mapping을 상속하게 되어 매핑의 모든 기능을 가지게 됩니다. Mapping은 추상 베이스 클래스임에도 불구하고 유용한 구체적인 메소드를 다수 제공합니다. 특히 다음과 같은 메소드는 상당히 유용합니다.

MutableMapping.update() :
이 메소드는 직접 호출할 수도 있지만, 다른 매핑이나 (key, value) 쌍의 반복형 및 키워드 인수에서 객체를 로딩하기 위해 __init__()에 의해 사용될 수도 있습니다. 이 메소드는 항목을 추가하기 위해서 'self[key] = value' 구문을 사용하므로 결국 서브클래스에서 구현한 __setitem__() 메소드를 호출하게 됩니다.
Mapping.get() :
StrKeyDict0에서는 __getitem__()과 일치하는 결과를 가져오기 위해 get() 메소드를 직접 구현해야 했지만, StrKeyDict에서는 StrKeyDict0.get()과 완전히 동일하게 구현된 Mapping.get()을 상속 받습니다.

Immutable Mappings

표준 라이브러리에서 제공하는 매핑 타입들은 모두 가변형이지만, 사용자가 실수로 매핑을 변경하지 못하도록 보장하고 싶은 경우가 있을 수 있습니다.

파이썬 3.3 이후 types 모듈은 MappingProxyType이라는 래퍼 클래스를 제공해서, 원래 매핑의 동적인 뷰를 제공하지만 읽기 전용의 mappingproxy 객체를 반환합니다. 따라서 원래 매핑을 변경하면 mappingproxy에 반영되지만, mappingproxy를 직접 변경할 수는 없습니다.

다음 코드는 mappingproxy를 사용하는 간단한 방법을 보여줍니다.

Dictionary Views

dict의 인스턴스 메소드인 .keys(), .values(), 그리고 .items()는 각각 dict_keys, dict_values, dict_items라는 클래스의 인스턴스를 반환합니다. 이 딕셔너리 뷰는 dict의 구현에서 내부 데이터 구조체의 read-only projections 입니다. Python 2에서 타겟 dict의 데이터를 복사한 리스트를 반환하는 동일한 메소드의 메모리 오버헤드를 피할 수 있게 해줍니다.

다음 예제 코드는 모든 딕셔너리 뷰에서 지원되는 기본 연산자들을 보여줍니다.

view 객체는 동적 프록시(dynamic proxy)입니다. 만약 원본 dict가 업데이트되면, 존재하는 view를 통해 변경된 부분을 즉시 확인할 수 있습니다.

dict_keys, dict_values, dict_items 클래스는 내부 클래스이며, __builtins__나 다른 표준 라이브러리 모듈을 통해서 사용할 수 없습니다. 심지어 이들 클래스의 참조를 가지고 있더라도 이를 이용하여 view를 생성할 수도 없습니다.

dict_values 클래스는 가장 단순한 딕셔너리 뷰입니다. 이는 오직 __len__, __iter__, __reversed__ 스페셜 메소드만 구현합니다. 이 메소드 이외에, dict_keys와 dict_items는 다른 set 메소드를 구현합니다.

Set Theory

파이썬에서 집합은 비교적 최근에 추가되었다고 볼 수 있으며, 그리 많이 사용되지는 않습니다. set 타입과 set의 불변타입인 frozenset은 파이썬 2.3에 모듈로 처음 등장했으며, 파이썬 2.6에서 built-in으로 승격되었습니다.

집합은 고유한 객체의 모음으로서, 기본적으로 중복 항목을 제거합니다.

집합의 요소들은 반드시 hashable해야 합니다. set은 해시 가능하지 않지만, frozenset은 해시 가능하므로, frozenset이 set에 들어갈 수 있습니다.

유니크하다는 것을 보장하는 것 이외에 집합 타입은 중위 연산자를 이용해서 기본적인 집합 연산을 구현합니다. 따라서 두 개의 집합 a, b가 있을 때, a | b는 합집합, a & b는 교집합, a - b는 차집합을 계산합니다. 집합 연산을 잘 사용하면 파이썬 프로그램의 소스 코드의 크기와 실행 시간을 줄일 수 있을 뿐만 아니라 루프나 조건절이 없어지므로 코드의 가독성이 높아집니다.

예를 들어 이메일 주소가 들어 있는 큰 집합(haystack)과 몇 가지 이메일 주소가 들어 있는 작은 집합(needles)이 있고, needles에 들어 있는 이메일 중 몇 개가 haystack 안에도 들어 있는지 알고 싶다고 가정해봅시다. 교집합(&) 연산자를 이용하면 다음과 같이 간단하게 작성할 수 있습니다.

found = len(needles & haystack)

교집합 연산자를 사용하지 않으면 위와 동일한 작업을 수행하기 위해 다음과 같이 구현해야 합니다.

found = 0
for n in needles:
    if n in haystack:
        found += 1

교집합 연산자를 사용한 코드는 사용하지 않은 코드보다 실행 속도가 약간 더 빠릅니다.

첫 번째로 살펴본 예제 코드는 두 객체가 모두 집합이어야 하는 반면, 두 번째 예제는 needles와 haystack이 iterable하다면 어느 객체든 사용할 수 있습니다. 하지만 객체가 집합형이 아니더라도 다음과 같이 즉석에서 집합으로 만들 수 있습니다.

found = len(set(needles) & set(haystack))

# or,
found = len(set(needles).intersection(haystack))

물론 위 코드에서는 집합을 만드는 추가 cost가 있지만, needles나 haystack 중 하나라도 이미 집합형이라면 방금 작성한 코드가 두 번째로 살펴본 코드보다 빨리 실행될 것입니다.

앞서 설명한 예제 모두 10,000,000개의 항목을 가진 haystack 안에서 1,000개의 항목을 3밀리초 안에 검색할 수 있습니다. 즉, 항목 하나를 검색하는 데 3마이크로초 정도 걸립니다.

내부의 해시 테이블 덕분에 집합 안에 속해 있는지 여부를 아주 빨리 검색할 수 있는 것 이외에도 set과 frozenset 타입은 새로운 집합을 생성하거나, set의 경우 기존 항목을 변경하는 다양한 연산을 제공합니다.

Set Literals

{1}, {1, 2} 등 집합 리터럴에 대한 구문은 수학적 표기법과 동일하지만, 공집합은 리터럴도 표기할 수 없으므로 반드시 set()으로 표기해야 합니다. 만약 이를 사용하지 않고 {} 구문을 사용하면 딕셔너리가 생성됩니다.

파이썬 3에서는 공집합 이외의 집합을 표준 문자열로 표현하기 위해 언제나 {} 구문을 사용합니다.

{1, 2, 3}과 같은 리터럴 집합 구문은 set([1, 2, 3])처럼 생성자를 호출하는 것보다 빠르고 가독성이 좋습니다. 생성자를 명시적으로 호출하는 경우에는 파이썬이 생성자를 가져오기 위해 집합명을 검색하고, 리스트를 생성하고, 이 리스트를 생성자에 전달해야 하므로 더 느립니다. 반면 {1, 2, 3}과 같은 리터럴 집합 구문을 처리하는 경우, 파이썬은 BUILD_SET이라는 특수 바이트코드를 실행합니다.

frozenset에 대한 별도의 리터럴 구문은 없으며, frozenset은 언제나 생성자를 호출해서 생성해야 합니다. 파이썬 3에서의 표준 문자열 표현은 frozenset 생성자를 호출하는 모습과 동일합니다.

Set Comprehensions

집합 컴프리헨션(setcomp)는 위에서 언급한 dictcomp와 함께 파이썬 2.7에서 추가되었습니다. 다음 코드는 이를 이용한 간단한 예제를 보여줍니다.

위 코드는 코드 번호가 32에서 255사이에 있는 문자 중 문자명 안에 'SIGN' 단어가 들어 있는 문자들의 집합을 생성합니다.

Set Operations

가변형과 불변형 집합에서 사용할 수 있는 메소드들은 다음과 같습니다.

이 메소드들 중 상당수는 연산자를 오버로딩하기 위한 스페셜 메소드입니다.

이외에 메소드들은 아래의 공식 문서를 참조하시길 바랍니다.

https://docs.python.org/3.10/library/stdtypes.html#set-types-set-frozenset

Built-in Types — Python 3.10.2 documentation

The following sections describe the standard types that are built into the interpreter. The principal built-in types are numerics, sequences, mappings, classes, instances and exceptions. Some collection classes are mutable. The methods that add, subtract,

docs.python.org

Internals of sets and dicts

파이썬이 어떻게 해시 테이블을 이용하여 딕셔너리와 집합을 구현하는지 알면, 이들의 장점과 단점을 이해하는데 도움이 됩니다. 이를 통해서 다음 질문에 대한 답들을 알아보도록 하겠습니다.

파이썬 dict와 set은 얼마나 효율적인가?
집합에는 왜 순서가 없을까?
dict의 키와 set 항목에는 왜 파이썬의 모든 객체를 사용할 수 없을까?
dict의 키는 왜 삽입 순서에 따라 다를까?
왜 set 요소들의 순서는 랜덤처럼 보일까?

A Performance Experiment

경험을 통해 dict와 set이 빠르다는 것은 알고 있습니다. 이번에는 통제된 실험을 통해서 이 내용을 확인해보도록 하겠습니다.

in 연산자로 검색할 때, dict, set, list의 크기가 성능에 미치는 영향을 확인하기 위해, double-precision 실수 천만 개로 구성된 배열 haystack을 생성하고 나서, haystack에 있는 500개의 실수와 haystack에 없는 500개의 실수로 구성된 needles 배열을 생성합니다.

먼저 다음의 코드를 통해서 실험에 사용할 데이터를 생성합니다.

"""
Generate data for container performance test
"""

import array
import random

MAX_EXPONENT = 7
HAYSTACK_LEN = 10 ** MAX_EXPONENT
NEEDLES_LEN = 10 ** (MAX_EXPONENT - 1)
SAMPLE_LEN = HAYSTACK_LEN + NEEDLES_LEN // 2

needles = array.array('d')

sample = {1 / random.random() for i in range(SAMPLE_LEN)}
print(f'initial sample: {len(sample)} elements')

# complete sample, in case duplicate random numbers were discarded
while len(sample) < SAMPLE_LEN:
    sample.add(1 / random.random())

print(f'complete sample: {len(sample)} elements')

sample = array.array('d', sample)
random.shuffle(sample)

not_selected = sample[:NEEDLES_LEN // 2]
print(f'not selected: {len(not_selected)} samples')
print('  writing not_selected.arr')
with open('not_selected.arr', 'wb') as fp:
    not_selected.tofile(fp)

selected = sample[NEEDLES_LEN // 2:]
print(f'selected: {len(selected)} samples')
print('  writing selected.arr')
with open('selected.arr', 'wb') as fp:
    selected.tofile(fp)

이렇게 데이터를 준비한 후에는 timeit 모듈을 이용해서 다음의 코드의 실행 시간을 측정합니다.

found = 0
for n in needles:
    if n in haystack:
        found += 1

그리고 각 컨테이너 별로 테스트를 위한 코드는 다음과 같습니다.

"""
Container ``in`` operator performance test
"""
import sys
import timeit

SETUP = '''
import array
selected = array.array('d')
with open('selected.arr', 'rb') as fp:
    selected.fromfile(fp, {size})
if {container_type} is dict:
    haystack = dict.fromkeys(selected, 1)
else:
    haystack = {container_type}(selected)
if {verbose}:
    print(type(haystack), end='  ')
    print('haystack: %10d' % len(haystack), end='  ')
needles = array.array('d')
with open('not_selected.arr', 'rb') as fp:
    needles.fromfile(fp, 500)
needles.extend(selected[::{size}//500])
if {verbose}:
    print(' needles: %10d' % len(needles), end='  ')
'''

TEST = '''
found = 0
for n in needles:
    if n in haystack:
        found += 1
if {verbose}:
    print('  found: %10d' % found)
'''

def test(container_type, verbose):
    MAX_EXPONENT = 7
    for n in range(3, MAX_EXPONENT + 1):
        size = 10**n
        setup = SETUP.format(container_type=container_type,
                             size=size, verbose=verbose)
        test = TEST.format(verbose=verbose)
        tt = timeit.repeat(stmt=test, setup=setup, repeat=5, number=1)
        print(f'|{size:{MAX_EXPONENT + 1}d}|{min(tt):f}')

if __name__ == '__main__':
    if '-v' in sys.argv:
        sys.argv.remove('-v')
        verbose = True
    else:
        verbose = False
    if len(sys.argv) != 2:
        print(f'Usage: {sys.argv[0]} <container_type>')
    else:
        test(sys.argv[1], verbose)

위 코드를 실행할 때, 인자로 실험할 컨테이너의 이름(dict, set, list)와 옵셔널로 -v 옵션을 추가해줄 수 있습니다.

예를 들면, 'python ./container_perftest.py dict'를 입력해주면 됩니다.

결과를 살펴보면, 제 컴퓨터에서 천개의 실수 키를 천 개의 항목을 가진 딕셔너리에서 검색하는 데 0.000091초, 천만 개의 항목을 가진 딕셔너리에서 검색하는 데 0.000517초가 걸렸습니다. 즉, 1천만 개의 항목을 가진 haystack에서 키 하나를 검색할 때, 약 517마이크로초의 시간이 걸린 셈입니다.

set의 결과는 다음과 같습니다.

list의 결과입니다.

여기서 추가로 교집합 연산의 실행 시간을 측정하기 위해서 for 루프가 아닌 다음의 코드로 변경하여 교집합 연산의 속도를 측정하였습니다. 위의 측정을 위한 코드에서 다음과 같이 변경해주면 됩니다.

SETUP = '''
import array
selected = array.array('d')
with open('selected.arr', 'rb') as fp:
    selected.fromfile(fp, {size})
if {container_type} is dict:
    haystack = dict.fromkeys(selected, 1)
else:
    haystack = {container_type}(selected)
if {verbose}:
    print(type(haystack), end='  ')
    print('haystack: %10d' % len(haystack), end='  ')
needles = array.array('d')
with open('not_selected.arr', 'rb') as fp:
    needles.fromfile(fp, 500)
needles.extend(selected[::{size}//500])
needles = set(needles)
if {verbose}:
    print(' needles: %10d' % len(needles), end='  ')
'''

TEST = '''
found = len(needles & haystack)
if {verbose}:
    print('  found: %10d' % found)
'''

이 연산을 사용하는 set의 측정 결과는 다음과 같습니다.

예상대로 & 연산자를 사용한 코드가 가장 빠르고, list가 가장 느립니다. 리스트에는 in 연산자 검색을 지원하는 해시 테이블이 없어서 전체 항목을 검색해야 하므로, 거의 haystack의 크기에 비례해서 시간이 소요됩니다.

프로그램에서 외부 장치로의 입출력을 수행한다면 dict나 set의 크기에 상관없이 키 검색 시간은 무시할 수 있을 정도로 작습니다.

Hash Tables in Dictionaries

이번에는 high-level의 관점에서 파이썬이 해시 테이블을 이용해서 dict을 구현하는 방법에 대해 살펴보겠습니다. CPython은 몇 가지 최적화 기법을 사용하고 있지만, 이에 대한 내용은 생략하고 전반적이 구조 위주로 살펴보겠습니다.

해시 테이블은 희소 배열(sparse array) 입니다. 일반적으로 해시 테이블의 셀을 버킷(bucket)이라고 부릅니다. dict 해시 테이블에는 각 항목 별로 버킷이 있고, 버킷에는 키에 대한 참조와 항목의 값에 대한 참조가 들어갑니다. 모든 버킷의 크기는 동일하므로, 오프셋을 계산하여 각 버킷에 바로 접근할 수 있습니다.

파이썬은 버킷의 1/3 이상을 비워두려고 노력합니다. 해시 테이블 항목이 많아지면 현재 크기의 2배의 공간을 할당하여 버킷 공간을 확보합니다.

해시 테이블 안에 항목을 넣을 때, 먼저 항목의 키에 대한 해시값을 계산합니다. 해시는 hash() 내장 함수를 이용해서 계산합니다.

Hashes and Equality

hash() 내장 함수는 내장 타입은 직접 처리하고 사용자 정의 타입의 경우에는 __hash__() 메소드를 호출합니다. 두 객체가 동일하면 이 값들의 해시값도 동일해야 합니다. 그렇지 않으면 해시 테이블 알고리즘이 제대로 동작하지 않습니다. 예를 들어, 정수 1과 실수 1의 내부 표현 형태는 다르지만, 1 == 1.0은 참이므로, hash(1) == hash(1.0)도 참이 되어야 합니다.

그리고 해시 테이블 인덱스처럼 효율성을 높이려면 해시값이 가능한 한 인덱스 공간에 골고루 퍼져야 합니다. 즉, 이상적으로는 비슷하지만 동일하지 않은 객체들의 해시값은 상당히 달라야 합니다. 아래 그림은 해시값의 비트 패턴을 비교한 것입니다. 1과 1.0의 해시값은 동일하지만, 1.0001, 1.0002, 1.0003의 해시값은 서로 상당히 다릅니다.

위의 결과를 출력하는 코드는 다음과 같습니다.

import sys

MAX_BITS = len(format(sys.maxsize, 'b'))
print(f'{MAX_BITS + 1}-bit Python build')

def hash_diff(o1, o2):
    h1 = f'{hash(o1):>0{MAX_BITS}b}'
    h2 = f'{hash(o2):>0{MAX_BITS}b}'
    diff = ''.join('!' if b1 != b2 else ' ' for b1, b2 in zip(h1, h2))
    count = f'!= {diff.count("!")}'
    width = max(len(repr(o1)), len(repr(o2)), 8)
    sep = '-' * (width * 2 + MAX_BITS)
    return (f'{o1!r:{width}} {h1}\n{" ":{width}} {diff} {count}\n'
            f'{o2!r:{width}} {h2}\n{sep}')

if __name__ == '__main__':
    print(hash_diff(1, 1.0))
    print(hash_diff(1.0, 1.0001))
    print(hash_diff(1.0001, 1.0002))
    print(hash_diff(1.0002, 1.0003))

The Hash Table Algorithm

my_dict[search_key]에서 값을 가져오기 위해 파이썬은 __hash__(search_key)를 호출해서 search_key의 해시값을 가져오고, 해시값의 최하위 비트를 해시 테이블 안의 버킷에 대한 오프셋으로 사용합니다(사용하는 비트 수는 현재 테이블의 크기에 따라 달라집니다. 간단하게 테이블의 크기로 모듈러 연산을 수행합니다). 찾아낸 버킷이 비어 있으면 KeyError를 발생시키고, 그렇지 않으면 버킷에 들어 있는 항목인 (found_key : found_value) 쌍을 검사해서 search_key == found_key인지 검사합니다. 이 값이 일치하면 항목을 찾은 것이므로 found_value를 반환합니다.

하지만 search_key와 found_key가 다른 경우에는 해시 충돌(hash collision)이 발생한 것입니다. 해시 충돌은 해시 함수가 임의의 객체를 적은 수의 비트로 매핑하기 때문에 발생합니다. 해시 충돌을 해결하기 위해 알고리즘은 해시의 다른 비트들을 가져와서 특정한 방식으로 조작한 후 그 결과를 이용해서 다른 버킷을 조회합니다. 이때 버킷이 비어 있으면 KeyError를 발생시킵니다. 그렇지 않고 키가 일치하면 항목 값을 반환하고, 키가 일치하지 않으면 다시 충돌 해결 프로세스를 반복합니다. 이 알고리즘을 다이어그램으로 표현하면 다음과 같습니다.

항목을 추가하거나 갱신하는 과정도 동일합니다. 다만 빈 버킷을 찾으면 새로운 항목을 추가하고, 동일한 키를 가진 버킷을 찾으면 버킷의 값을 새로운 값으로 갱신합니다.

그리고 항목을 추가할 때 해시 테이블에 항목이 너무 많다고 판단되면 파이썬은 더 큰 공간을 가진 해시 테이블을 새로운 위치에 다시 만듭니다. 해시 테이블이 커지면 더 많은 해시 비트를 버킷 오프셋으로 사용하며, 더 많은 비트를 사용할수록 충돌할 가능성은 낮아집니다.

해시 테이블을 이렇게 구현하려면 상당히 많은 작업이 필요할 것으로 보이지만, dict 안에 수백만 개의 항목이 있어도 대부분 충돌없이 검색이 되는 경우가 많고, 한 번 검색할 때마다 발생하는 평균 충돌 횟수는 1~2회입니다. 일반적으로 운이 아주 나쁘더라도 몇 번의 충돌 이후에 원하는 항목을 찾을 수 있습니다.

Practical Consequences of How dict Works

이번에는 dict에서 사용하는 해시 테이블의 한계와 장점들에 대해 알아보겠습니다.

Keys must he hashable objects

다음 요구 사항은 만족하는 객체는 hashable 합니다.

객체의 lifetime 동안 언제나 동일한 값을 반환하는 __hash__() 메소드를 제공해서 hash() 함수를 지원한다
__eq__() 메소드를 통해 동치성(equality)을 판단할 수 있다
a == b가 참이라면, hash(a) == hash(b)도 반드시 참이어야 한다

사용자 정의 자료형은 id()를 해시값으로 사용하고 모든 객체는 서로 동일하지 않으므로 기본적으로 해시 가능합니다.

dicts have significant memory overhead

dict가 내부적으로 해시 테이블을 사용하고 있고 해시가 제대로 동작하려면 빈 공간이 충분해야 하므로, dict의 메모리 공간 효율성은 그리 높지 않습니다. 예를 들어 많은 양의 레코드를 처리하는 경우, JSON 형태로 각 레코드에 하나의 dict을 할당해서 딕셔너리의 리스트를 사용하는 것보다 튜플이나 namedtuple의 리스트에 저장하는 것이 좋습니다. dict을 튜플로 교체하면, 레코드마다 하나의 해시 테이블을 가져야 하는 부담과 레코드마다 필드명을 다시 저장해야 하는 부담을 제거함으로써 메모리 사용량을 줄일 수 있습니다.

사용자 정의 타입의 경우 __slots__ 클래스 속성을 이용해서 객체 속성 저장소를 dict에서 튜플로 변경할 수 있습니다.

Key search is very fast

dict는 속도를 위해 공간을 포기하는 것이라고 보면 됩니다. 딕셔너리는 메모리 오버헤드가 상당히 크지만, 메모리에 로딩되는 한 딕셔너리 크기와 무관하게 빠른 속도를 제공합니다. 위에서 dict 크기를 1,000에서 10,000,000으로 증가시켰을 때, 검색 시간은 5~6배 정도 증가했을 뿐입니다.

Key ordering depends on insertion order

해시 충돌이 발생하면 두 번째 키는 충돌이 발생하지 않았을 때의 정상적인 위치와 다른 곳에 위치하게 됩니다. 따라서 dict([key1, value1), (key2, value2)])로 생성한 딕셔너리와 dict([key2, value2), (key1, value1)])으로 생성한 딕셔너리는 동일하지만, key1과 key2의 해시가 충돌하면 키의 순서는 달라집니다.

다음 예제는 동일한 데이터를 가진 3개의 딕셔너리를 다른 순서로 로딩한 결과를 보여줍니다. 생성된 딕셔너리는 순서는 달라도 모두 동일하다고 판단됩니다.

DIAL_CODES = [
    (82, 'Korea'),
    (91, 'India'),
    (1, 'United States'),
    (62, 'Indonesia'),
    (55, 'Brazil'),
    (92, 'Pakistan'),
    (880, 'Bangladesh'),
    (234, 'Nigeria'),
    (7, 'Russia'),
]

d1 = dict(DIAL_CODES)
print('d1:', d1.keys())

d2 = dict(sorted(DIAL_CODES))
print('d2:', d2.keys())

d3 = dict(sorted(DIAL_CODES, key=lambda x: x[1]))
print('d3:', d3.keys())

assert d1 == d2 and d2 == d3

Adding items to a dict may change the order of existing keys

dict에 항목을 추가할 때마다 파이썬 인터프리터는 그 딕셔너리의 해시 테이블 크기를 늘릴지 판단합니다. 그리고 더 큰 해시 테이블을 새로 만들어서 기존 항목을 모두 새 테이블에 추가합니다. 이 과정 동안 기존과 다르게 해시 충돌이 발생해서 새로운 해시 테이블에서의 키 순서가 달라질 수 있습니다. 이 모든 것은 구현된 알고리즘에 따라 달라지므로, 이 현상이 언제 발생할지 정확히 예측할 수는 없습니다. 그리고 딕셔너리 키를 반복하는 도중에 항목을 변경하는 경우에는 원하는 항목을 검색하지 못하는 경우가 발생할 수 있습니다. 심지어 항목을 추가하기 전에 이미 있던 항목도 제대로 검색하지 못할 수 있습니다.

따라서 딕셔너리를 반복하는 동안 딕셔너리의 내용을 변경하는 것은 좋지 않은 방법입니다. 딕셔너리를 검색하면서 항목을 추가해야 하는 경우 다음의 두 단계로 수행합니다.

처음부터 끝까지 딕셔너리를 검색하면서 필요한 항목은 별도의 딕셔너리에 추가한다
별도의 딕셔너리로 원래 딕셔너리를 갱신한다

How Sets Work - Practical Consequences

set과 frozenset도 해시 테이블을 이용해서 구현하지만, 각 버킷이 항목에 대한 참조만을 담고 있다는 점이 다릅니다 (항목 자체가 dict에서의 키처럼 사용되지만, 이 키를 통해 접근할 값이 없습니다).

위에서 설명한 dict의 동작을 결정하는 방식이 집합에도 모두 적용되므로, set에 대한 설명은 다음과 같이 정리할 수 있습니다.

set 요소는 모두 hashable 해야 한다
set의 메모리 오버헤드는 매우 크다
집합에 속해 있는지 확인하는 검사는 매우 효율적이다
요소의 순서는 요소를 추가한 순서에 따라 달라진다
요소를 집합에 추가하면 다른 요소의 순서가 바뀔 수 있다

'프로그래밍 > Python' 카테고리의 다른 글

[Python] 객체 참조, 가변성, 재활용 (0)	2022.03.16
[Python] 텍스트와 바이트 (0)	2022.03.15
[Python] 시퀀스 (Sequences) - (2) (0)	2022.03.12
[Python] 시퀀스 (Sequences) - (1) (0)	2022.03.12
[Python] 파이썬 데이터 모델 (Data Model) (0)	2022.03.11

별준

[Python] 딕셔너리와 집합

References

Contents

Standard API of Mapping Types

What is Hashable ?

Dict Comprehensions

Overview of Common Mapping Methods

Handling Missing Keys with setdefault()

Mappings with Flexible Key Lookup

defaultdict: Another Take on Missing Keys

missing() 메소드

Variations of dict

Subclassing UserDict (custome mappings)

Immutable Mappings

Dictionary Views

Set Theory

Set Literals

Set Comprehensions

Set Operations

Internals of sets and dicts

A Performance Experiment

Hash Tables in Dictionaries

Hashes and Equality

The Hash Table Algorithm

Practical Consequences of How dict Works

Keys must he hashable objects

dicts have significant memory overhead

Key search is very fast

Key ordering depends on insertion order

Adding items to a dict may change the order of existing keys

How Sets Work - Practical Consequences

'프로그래밍 > Python' 카테고리의 다른 글

댓글

티스토리툴바

[Python] 딕셔너리와 집합

References

Contents

Standard API of Mapping Types

What is Hashable ?

Dict Comprehensions

Overview of Common Mapping Methods

Handling Missing Keys with setdefault()

Mappings with Flexible Key Lookup

defaultdict: Another Take on Missing Keys

__missing__() 메소드

Variations of dict

Subclassing UserDict (custome mappings)

Immutable Mappings

Dictionary Views

Set Theory

Set Literals

Set Comprehensions

Set Operations

Internals of sets and dicts

A Performance Experiment

Hash Tables in Dictionaries

Hashes and Equality

The Hash Table Algorithm

Practical Consequences of How dict Works

Keys must he hashable objects

dicts have significant memory overhead

Key search is very fast

Key ordering depends on insertion order

Adding items to a dict may change the order of existing keys

How Sets Work - Practical Consequences

'프로그래밍 > Python' 카테고리의 다른 글

관련글

댓글

티스토리툴바

missing() 메소드