Fluent Python (챕터 3)

딕셔너리와 집합

 

dict 형은 애플리케이션에서 뿐만 아니라, 파이썬 구현의 핵심 부분이기도 하다. 모듈 네임스페이스, 클래스 및 인스턴스 속성, 함수의 키워드 인수 등 핵심 부분에 딕셔너리가 사용되고 있다. 내장 함수들은 __builtins__.__dict__에 들어 있다.

 

파이썬 dict 클래스는 상당히 최적화되어 있는데, 이는 해시 테이블이라는 엔진 덕분이다.

dict 의 키는 해시 가능해야 한다.

수명 주기 동안 절대 변하지 않는 해시값을 갖고 있고(__hash__() 메서드 필요) 다른 객체와 비교할 수 있으면(__eq__()메서드) 객체를 해시 가능하다고 한다. 동일하다고 판단되는 객체는 반드시 해시값이 동일해야 한다.

불변 내장 객체는 모두 해시 가능하다고 하는 경우도 있는데, 튜플은 내부에 해시 불가능한 객체를 참조할 수 있기 때문에 항상 옳은 것은 아니다.

사용자 정의 자료형은 기본적으로 해시 가능하며, 객체가 자신의 내부 상태를 평가해서 __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, "two": 2, "one": 1})
print(a == b == c == d == e)

> True

 

dict 형도 listcomp, genexp 처럼 지능형 딕셔너리 기능을 구현할 수 있다.

DIAL_CODES = [
    (86, 'China'),
    (91, 'India'),
    (1, 'USA'),
    (55, 'Brazil'),
]

country_code = {country: code for country, code in DIAL_CODES}
print(country_code)

> {86: 'China', 91: 'India', 1: 'USA', 55: 'Brazil'}

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

> {1: 'USA', 55: 'BRAZIL'}

 

dict  뿐만 아니라 여러 매핑형이 기본적으로 제공하는 API 는 매우 다양하다.

그 중에서도 update(m, [**kargs]) 메서드가 첫 번째 인수 m을 다루는 방식은 덕 타이핑(duct typing) 의 대표적인 사례이다. 먼저 m 이 keys() 메서드를 갖고 있는지 확인한 후, 만약 메서드를 갖고 있으면 매핑이라고 간주한다. keys() 메서드가 없으면 m 의 항목들이 (키, 값) 쌍으로 되어 있다고 간주하고 m을 반복한다.

 

dict는 fail-fast 철학에 따라, 존재하지 않는 키 k로 d[k]를 접근하면 오류를 발생시킨다. 많은 파이썬 개발자들이 KeyError 를 처리하는 것보다 기본값을 사용하는 것이 더 편리한 경우에는 d.get(k, default) 를 사용한다. 하지만 이에 대한 좋지 않은 사례들도 있다.

 

WORD_RE = re.compile('\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 like this to make a point
            occurrences = index.get(word, [])  # <1>
            occurrences.append(location)       # <2>
            index[word] = occurrences          # <3>

# print in alphabetical order
for word in sorted(index, key=str.upper):  # <4>
    print(word, index[word])
    
Although [(11, 1), (16, 1), (18, 1)]
ambiguity [(14, 16)]
and [(15, 23)]
are [(21, 12)]
aren [(10, 15)]
at [(16, 38)]
bad [(19, 50)]
...

특정 텍스트 문서에서 한 줄씩 읽어오며, 각 단어와 그 단어가 나타난 행, 열 번호를 쌍으로 보여주는 코드이다.

위 코드에서 index 에 해당 단어가 있는지를 확인하고 없으면 빈 리스트를 가져온다. 그리고 location 을 리스트에 저장한 뒤, 다시 인덱스에 넣는다. 이 때, 인덱스를 한 번 더 검색하는 비효율이 발생한다.

 

이 때, setdefault 를 사용하면 간단하게 구현할 수 있다.

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)  # <1>

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

sefdefault 가 값을 바로 반환하므로, 다시 검색할 필요 없이 바로 갱신이 가능하다.

 

my_dict = {}
key = "key"
new_value = 'value'

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

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

두 코드의 결과는 같다. 하지만 두 번째 코드는 키를 두 번 검색하는 반면, setdefault 는 한 번만 검색한다.

 

dict 에서 검색할 때, 키가 존재하지 않으면 특별한 값을 반환하는 매핑이 있으면 편한 경우가 있다. 이 때, 두 가지 방법이 있다. 하나는 defaultdict 를 사용하는 것이고, 또다른 하나는 dict 등의 매핑형을 상속해서 __missinig__() 메서드를 추가하는 방법이다.

 

defaultdict 는 객체를 생성할 때, 존재하지 않는 키 인수로 __getitem__() 메서드를 호출할 때마다 기본값을 생성하기 위해 사용되는 콜러블을 제공한다. 이 콜러블은 default_factory 라는 객체 속성에 저장된다.

 

예를 들어, dd = defaultdict(list) 코드로 객체를 생성한 후 존재하지 않는 키인 'new-key' 로 dd['new-key'] 표현식을 수행하면 아래와 같다.

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

default_factory 가 설정되어 있지 않으면 KeyError 가 발생한다.

실제 defaultdict 가 default_factory 를 호출하게 만드는 메커니즘은 __missing__() 특수 메서드에 의존하며, 표준 매핑형은 모두 이 기능을 지원한다.

 

__missing__() 메서드는 존재하지 않는 키를 처리한다. dict 클래스를 상속하고 __missing__() 메서드를 정의하면, dict.__getitem__() 표준 메서드가 키를 발견할 수 없을 때 KeyError 를 발생시키지 않고 __missing__() 메서드를 호출한다.

 

__missing__() 메서드는 d[k] 연산자를 사용하는 경우 등 __getitem__() 메서드를 사용할 때만 호출된다. in 연산자를 구현하는 get() 이나 __contains__() 메서드 등 키를 검색하는 다른 메서드에는 __missing__() 메서드가 영향을 미치지 않는다.

 

Tests for item retrieval using `d[key]` notation::

    >>> d = StrKeyDict0([('2', 'two'), ('4', 'four')])
    >>> d['2']
    'two'
    >>> d[4]
    'four'
    >>> d[1]
    Traceback (most recent call last):
      ...
    KeyError: '1'

Tests for item retrieval using `d.get(key)` notation::

    >>> d.get('2')
    'two'
    >>> d.get(4)
    'four'
    >>> d.get(1, 'N/A')
    'N/A'


Tests for the `in` operator::

    >>> 2 in d
    True
    >>> 1 in d
    False

다음 테스트를 만족하는 StrKeyDict0 은 아래와 같이 정의할 수 있다.

 

class StrKeyDict0(dict):  # <1>

    def __missing__(self, key):
        if isinstance(key, str):  # <2>
            raise KeyError(key)
        return self[str(key)]  # <3>

    def get(self, key, default=None):
        try:
            return self[key]  # <4>
        except KeyError:
            return default  # <5>

    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()  # <6>

 

<3> 과정을 통해서 key 가 반드시 문자열이 아니더라도 검색 가능하게 도와준다. 단, 2번 과정을 통해서 해당 키가 문자열로 변경해도 존재하지 않을 때에는 KeyError 를 발생시킨다. 4번 과정에서는 __getitem__() 메서드를 통해서 값이 있으면 그 값을 리턴하고 아니면 __missing__() 메서드를 거친다. 이 때 KeyError 가 발생하면, __missing__() 에서도 찾지 못했다는 것을 의미하므로 default 를 반환한다. 

__contains__() 메서드는 키가 없는 경우에 __missing__() 메서드를 호출하지 않으므로, 키 값의 자료형을 다르게 한 경우에는 테스트와 같은 결과가 나올 수 없다. 따라서 위와 같이 명시적으로 키를 조회한다. 이 때, k in my_dict 형태로 조회하지 않는다. __contains__() 를 재귀적으로 호출하기 때문이다.

 

참고) key 의 존재 여부를 확인할 때, k in my_dict.keys() 와 같은 형태가 더 효율적이다. my_dict.keys() 는 KeyView 를 반환하는데, 이는 집합과 비슷하므로 리스트보다 포함 여부를 판단할 때 더 빠르다.

 

 

그 외 매핑형으로는 collections.OrderedDict, collections.ChainMap, collections.Counter 등이 있다.

OrderedDict 는 키를 삽입한 순서대로 유지함으로써 항목을 반복하는 순서를 예측할 수 있다. 그러나 파이썬 3.7 부터는 dict 자체가 기본 순서를 유지하게 되어서 굳이 사용할 일이 없을 것 같다.

ChainMap 은 매핑들의 목록을 담고 있으며 한꺼번에 검색이 가능하다.

from collections import ChainMap
print(ChainMap(locals(), globals()))

 

Counter 는 모든 키에 정수형 카운터를 갖고 있는 매핑이며, 객체의 수를 세기 위해 사용한다.

from collections import Counter

print(Counter('abracadabra'))
> Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

 

기본적으로 사용자 정의 매핑은 UserDict 를 상속해서 사용하는 것이 좋다.

내장형에서는 아무런 문제 없이 상속할 수 있는 메서드들을 오버라이드 해야 하는 구현의 특이성 때문에 dict보다는 UserDict 를 상속하는 것이 낫다.

 

UserDict는 내부에 실제 항목을 담고 있는 data 라고 하는 dict 객체를 갖고 있다.

import collections


class StrKeyDict(collections.UserDict):  # <1>

    def __missing__(self, key):  # <2>
        if isinstance(key, str):
            raise KeyError(key)
        return self[str(key)]

    def __contains__(self, key):
        return str(key) in self.data  # <3>

    def __setitem__(self, key, item):
        self.data[str(key)] = item   # <4>

<4> 에서 모든 키를 str 형으로 저장하여 비문자열 키로 객체를 생성하거나 갱신할 때 발생할 수 있는 예기치 못한 문제를 피하게 해준다.  <3> 에서는 모든 키가 str 형이므로 보다 간단하게 data 객체에서 바로 조회 가능하다.

 

불변 스퀀스에 여러 종류가 있듯, 불변 딕셔너리도 존재한다.

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

 

from types import MappingProxyType

d = {1: "A"}
d_prodxy = MappingProxyType(d)
print(d_prodxy)
> {1: 'A'}

print(d_prodxy[1])
> A

d_prodxy[2] = "B"

Traceback (most recent call last):
  File "chapter_3.py", line 42, in <module>
    d_prodxy[2] = "B"
TypeError: 'mappingproxy' object does not support item assignment

d[2] = "B"
print(d_prodxy)
> {1: 'A', 2: 'B'}

print(d_prodxy[2])
> B

---

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

집합 요소는 반드시 해시할 수 있어야 한다. set은 해시 가능하지 않지만 frozenset 은 해시 가능하므로, frozenset은 set에 들어갈 수 있다.

 

고유함을 보장하는 것 이외에 집합형은 중위 연산자를 이용해서 기본적인 집합 연산을 구현한다.

a | b (합집합), a & b (교집합), a - b(차집합) 으로 표현 가능하다.

 

집합 연산을 현명하게 이용하면 소스 코드의 크기와 실행 시간을 줄일 수 있을 뿐만 아니라, 루프나 조건절이 없어지므로 코드의 가독성이 높아진다.

예를 들어, 이메일 주소가 있는 큰 집합(haystack) 과 몇 가지 이메일 주소가 들어 있는 작은 집합(needles)이 있고 needles 에 들어 있는 이메일 중 몇 개가 haystack 안에도 들어 있는지 알고 싶다고 가정하자.

이 때, 교집합 연산자를 이용하면 간단하게 표현 가능하다.

found = len(needles & haystack)

이를 교집합 연산자 없이 구현하면 아래와 같다.

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

 

먼저 첫 번째 코드는 반드시 두 객체 모두 집합이어야 하는 반면, 두 번째 코드는 반복 가능한 어느 객체든 사용 가능하다. 속도는 집합의 연산자를 사용하는 것이 빠르다.

그러나 객체가 집합형이 아니더라도 즉석에서 집합으로 만들 수 있다.

found = len(set(needles).intersection(haystack)

10,000,000 개의 항목을 가진 haystack 안에서 1000개의 항목을 3밀리초 안에 검색할 수 있다. 즉, 항목 하나를 검색하는 데 3마이크로초 정도 걸린다.

 

공집합은 {} 가 아닌 set() 구문을 사용해야 한다. {} 은 빈 딕셔너리를 생성한다. 하지만 그 외의 집합은 {1, 2, 3} 형태로 생성한다. set([1, 2, 3]) 으로 생성자를 호출하는 것보다 더 빠르고 가독성도 좋다. 생성자를 명시적으로 호출하는 경우에는 파이썬 생성자를 가져오기 위해 집합명을 검색하고, 리스트를 생성하고, 이 리스트를 생성자에 전달해야 하므로 더 느리다.

 

from dis import dis
print(dis('{1}'))

  1           0 LOAD_CONST               0 (1)
              2 BUILD_SET                1
              4 RETURN_VALUE


print(dis('set([1])'))

  1           0 LOAD_NAME                0 (set)
              2 LOAD_CONST               0 (1)
              4 BUILD_LIST               1
              6 CALL_FUNCTION            1
              8 RETURN_VALUE

 

frozenset에 대한 별도의 리터럴 구문은 없으며 언제나 생성자를 호출해서 생성한다.

frozenset(range(10))
> frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9})

 

지능형 집합도 사용 가능하다.

from unicodedata import name
print({chr(i) for i in range(32, 256) if 'SIGN' in name(chr(i), '')})

> {'+', '£', '×', '§', '¶', '¥', '©', '%', '®', '<', '#', '÷', 'µ', '¢', '¤', '>', '=', '¬', '±', '°', '$'}

 

딕셔너리와 집합은 성능 실험을 했을 때, 항목이 커질수록 리스트에 비해 상당히 빠르다. 어떻게 이러한 속도가 나올 수 있는지 알아본다.

 

파이썬은 해시 테이블을 이용해서 딕셔너리를 구현한다. 해시 테이블은 배열 안의 요소의 위치가 연속적이지 않고, 배열의 길이보다 요소의 개수가 항상 적은 희소 배열이다. 해시 테이블 안의 항목을 버킷이라고 하는데, 버킷에는 키에 대한 참조와 항목의 값이 들어간다. 모든 버킷의 크기가 동일하므로 오프셋을 계산해서 각 버킷에 바로 접근할 수 있다.

파이썬은 버킷의 1/3 이상을 비워두려고 노력한다. 해시 테이블 항목이 많아지면 더 넓은 공간에 복사해서 버킷 공간을 확보한다. 해시 테이블 안에 항목을 넣을 때, 먼저 항목 키의 해시값을 계산한다. 해시는 hash() 내장 함수를 이용해서 계산한다.

 

hash() 내장 함수는 내장 자료형은 직접 처리하고 사용자 정의 자료형의 경우 __hash__() 메서드를 호출한다. 두 객체가 동일하면 이 값들의 해시값도 동일해야 한다. 그렇지 않으면 해시 테이블 알고리즘이 제대로 작동하지 않는다.

예를 들면 1 == 1.0 이므로 hash(1) == hash(1.0) 이어야 한다.

그리고 효율성을 높이려면 해시값이 가능한 한 인덱스 공간에 골고루 퍼져야 한다. 즉, 이상적으로는 비슷하지만 동일하지 않는 객체들의 해시값은 상당히 달라야 한다. 파이썬에서 해시값의 비트 패턴을 비교했을 때, 1과 1.0의 해시값은 동일하지만 1.0001, 1.0002의 해시값은 서로 상당히 다른 것을 볼 수 있다.

print(hash(1))
> 1

print(hash(1.001))
> 2305843009213441

 

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

 

하지만 두 키가 일치하지 않으면 해시 충돌(hash collision) 이 발생한 것이다. 해시 충돌은 해시 함수가 임의의 객체를 적은 수의 비트로 매핑하기 때문에 발생한다. 해시 충돌을 해결하기 위해 다른 비트들을 가져와서 특정한 방식으로 조작한 후 그 결과를 이용해서 다른 버킷을 조회한다. 

 

dict에서 사용하는 해시 테이블의 한계와 장점은 아래와 같다.

 

dict의 메모리 오버헤드가 크다. 

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

사용자 정의 자료형의 경우 __slots__ 클래스 속성을 이용하여 객체 속성 저장소를 dict에서 튜플로 변경할 수 있다.

 

키 검색이 아주 빠르다.

- dict는 속도를 위해 공간을 포기하는 예다. 딕셔너리는 메모리 오버헤드가 상당히 크지만, 메모리에 로딩되는 한 딕셔너리 크기와 무관하게 빠른 접근 속도를 제공한다. 

 

키 순서는 삽입 순서에 따라 달라진다.

- 해시 충돌이 발생하면 두 번째 키는 정상적인 위치와 다른 곳에 놓이게 된다.

 

딕셔너리에 항목을 추가하면 기존 키의 순서가 변경될 수 있다.

- dict에 항목을 추가할 때마다 파이썬 인터프리터는 그 딕셔너리의 해시 테이블 크기를 늘릴지 판단한다. 그리고 더 큰 해시 테이블을 새로 만들어서 기존 항목을 모두 새 테이블에 추가한다. 이 과정에서 기존과 다르게 해시 충돌이 발생해서 새로운 해시 테이블에서의 키 순서가 달라질 수 있다. 따라서 딕셔너리를 반복하는 동안 딕셔너리의 내용을 변경하는 것은 좋지 않은 방법이다. 

 

set과 frozenset도 해시 테이블을 이용해서 구현하지만, 각 버킷이 항목에 대한 참조만 담고 있다는 점이 다르다. 그 외에는 위의 설명이 집합에도 동일하게 적용된다.

 

 

정리

파이썬의 딕셔너리는 해시 테이블 기반으로 한 최적화된 기능들을 제공한다.

딕셔너리는 속도를 위해 공간을 포기한 데이터 타입이라고 할 수 있다. 딕셔너리는 키와 값의 쌍이며, 키는 해시 가능해야한다. 해시 가능해야 함은 해시 값을 가지며, 비교 가능해야 함을 말한다. 동일한 해시값을 가진 객체는 반드시 동일한 객체여야 한다.

내부적으로 __hash__(), __eq__() 메서드를 호출한다.

딕셔너리도 지능형 딕셔너리 구문을 사용할 수 있다.

딕셔너리는 fast-fail 철학에 따라서 키가 존재하지 않는 경우에 KeyError 를 일으킨다. 이러한 점을 보완하여 더 효율적인 코딩을 가능하게 하는 setdefault, defaultdict 등의 상황에 따라 매핑형을 사용할 수도 있다.

d[k] 와 같은 연산자를 통해 __getitem__() 메서드를 사용하는 매핑형은 __missing__() 메서드를 정의함으로써, 키가 존재하지 않을 때 단순히 KeyError를 일으키지 않고 해당 상황에 대한 처리를 추가할 수 있다.

in 연산자와 같이 내부적으로 __contains__() 메서드를 호출하는 경우에는 __missing__() 메서드를 호출하지 않는다.

collecions 모듈에 OrderedDict, Counter, ChainMap 등의 매핑형도 존재한다.

일반적으로 사용자 정의 매핑형을 구현하는 경우에는 dict 보다는 UserDict 객체를 상속받는 것이 불필요한 메서드 오버라이딩을 하지 않는 효과적인 방법이다.

UserDict 는 내부적으로 data 라는 속성에 dict 객체를 담고 있다.

types 모듈 안에 MappingProxyType 이라는 불변 딕셔너리가 있다. 이는 mappingproxy 라는 읽기 전용의 객체를 반환하며, 원본 매핑을 수정할 수는 있지만 mappingproxy 객체로 접근하여 값을 변경할 수는 없다.

집합은 고유한 객체의 모음으로 기본적으로 중복을 제거한다. 교집합, 합집합, 차집합 등의 연산을 제공하며, 이를 잘 활용하여 반복문이나 조건문 없이 가독성 좋고 효율적인 코드를 작성할 수 있다.

지능형 집합도 구현할 수 있으며 공집합은 반드시 set() 생성자를 통해서 생성해야 한다.

리터럴 구문이 생성자를 통한 방법보다 빠르다.

파이썬 딕셔너리를 구현하는 해시 테이블은 배열 안의 요소의 위치가 연속적이지 않으며 배열의 전체 길이보다 요소의 개수가 항상 적은 희소 배열이다. 해시 테이블의 버킷 안에는 키에 대한 참조와 항목의 값이 들어간다. 

hash() 내장함수는 키의 해시 값을 계산한다. 사용자 정의 매핑형은 __hash__() 메서드를 통해서 해시값을 계산한다.

해시테이블의 효율성을 높이기 위해서는 인덱스 공간 안에 골고루 분포해야 한다. 즉, 비슷한 값의 해시값 차이가 커야 한다.

찾고자 하는 키 값과 버킷 안의 키가 서로 다른 경우는 해시 충돌이라고 하며, 이는 키를 해싱하는 해시 함수가 적은 비트 수로 매핑하기 때문에 발생한다. 이 때, 다른 비트들을 가져와서 조작한 후 그 결과를 이용해서 다른 버킷을 조회한다.

해시 테이블 관련 참고: https://velog.io/@monsterkos/TIL-2020.08.18

TIL (2020.08.18)(1)

해시 테이블의 장점과 한계는 다음과 같다.

- 메모리 오버해드가 크다.

- 키 검색이 매우 빠르다.

- 키 순서는 삽입 순서에 따라 다르다.

- 항목을 추가하면 기존 키의 순서가 변경될 수 있다.

 --> 마지막은 파이썬 3.6 버전부터 dict의 순서를 보장하게끔 수정되어 보완이 되지 않았나 싶다.