Fluent Python Chapter 3. Dictionary (feat. hashtable)

Chapter1의 Introduction 부분에서 이야기 한 것 처럼 지난 5년간 다양한 언어나 소프트웨어를 공부하고 이용하여 소프트웨어를 개발했는데 이것 저것 하다보니 자주 사용하는 언어임에도 불구하고 파이썬을 잘 활용하고 있느냐에 대한 답변을 자신있게 하기 어렵다고 느껴서 Fluent Python이라는 책을 공부하며 정리하고 있습니다. 올 해에는 새로운 기술들을 좋지만 기존에 활용하던 언어나 프레임워크 그리고 소프트웨어를 더 잘 사용할 수 있도록 깊게 공부할 수 있는 한해를 만들고 싶은 소망이 있습니다.

 

2월 안에 모든 Chapter를 읽고 정리하는게 목표인데 조금 속도를 올려야 겠습니다.

 

지난 chapter 정리

Fluent Python Chapter 1. 파이썬 데이터 모델 (Feat. 일관성 있는 언어)

Fluent Python Chapter 2-1. Sequence (Sequence의 분류, listcomp, generator, tuple, slicing

Fluent Python Chapter 2-2. Sequence (bisect, deque, memoryview)

 

HashTable

책에서 내용 상 가장 뒤지만 저는 가장 중요하다고 생각해서 앞에서 정리를 해보겠습니다.

파이썬에서 list와 더불어 가장 많이 활용하는 데이터 모델은 dictionary라고 생각합니다. 파이썬 내부 구현에서도 정말 많이 쓰이고 있습니다. (모듈 네임스페이스, 클래스 및 인스턴스 속성 등) 이렇게 많이 사용하는데는 정말 편한 인터페이스로 빠르게 원하는 데이터를 찾을 수 있기 때문입니다. 빠르게 원하는 데이터를 찾을 수 있는 이유는 dictionary가 Hashtable이라는 자료구조로 만들어졌기 때문입니다.

 

dictionary의 Hashtable을 high level로 살펴보면 아래와 같습니다. (저의 추측입니다. 정확한 구현은 cpython 코드를 확인하셔야 합니다. 혹시, 잘못 된 부분이 있다면 편하게 알려주세요! )

 

예시: 2개의 key, value가 들어있는 dictionary

	offset	key reference	value reference
bucket 0	0
bucket 1	1	0xaaaddd (예시)	0xddddd (예시)
bucket 2	2
bucket 3	3	0xaaad12 (예시)	0xdddd98 (예시)
bucket 4	4

각 bucket은 크기가 동일합니다. 그렇기 때문에 offset으로 해당 메모리에 바로 접근할 수 있습니다. 

hashtable인 이유는 key의 hash 함수를 활용해서 offset(위치)가 결정됩니다. 보통 hash(key) 값에 masking bit 를 AND 연산에서 위치가 결정됩니다. key는 불변형이어야 합니다. (ex. list는 가변형이라 key가 될 수 없음. hash값이 바뀔 수 있기 때문에)

위에 보신 것 처럼 비어있는 bucket도 있습니다. 파이썬은 1/3의 이상을 비워두려고 노력한다고 합니다. 그래서 새로운 key, value를 assign할 때 새로운 hashtable로 옮길지를 결정합니다. 마지막으로 중요한 부분 중 하나인 offset이 겹칠 때(해시충돌)는 linear probing(상위 비트를 사용)를 통해 다시 offset을 설정합니다.

 

한 번 위에서 나온 내용을 정리하면 아래와 같습니다.

 - dictionary는 hashtable이라는 자료구조로 되어 있다.

 - hashtable은 key의 hash값을 이용해서 offset을 찾고, 모든 버킷은 같은 크기이기 때문에 offset을 통해서 바로 접근할 수 있다. (시간 복잡도 O(1)

 - 서로 다른 키가 같은 offset을 같는 경우(해시충돌) linear probing을 이용해서 새로운 offset에 저장한다.

 

이 정리한 내용을 바탕으로 책에서 나온 질문들에 답을 해보려고 합니다. (dictonary가 어떻게 구현되었는지를 이해하면 답변 할 수 있습니다!)

 

- 왜 순서가 없을까?

-> 아까 본 것 처럼 가장 먼저 넣는다고 offset 0인 메모리에 저장되지 않는다. key의 hash값을 이용해서 offset이 결정되고, 같은 offset이 나오는 경우에도 먼저 넣는 key에 따라서 순서가 다름. (즉, 같은 key도 항상 같은 table의 offset에 저장되지 않음.)

 

- dict의 key와 set 항목에 모든 객체를 사용할 수 없는 이유는 무엇인가?

-> hash함수를 이용해서 offset이 결정되기 때문에 hashable한 객체만 가능하다. list같은 가변형 객체는 값이 바뀔 수 있기 때문에 hashable하지 않다.

 

- dict의 키와 set 항목의 순서가 왜 삽입순서에 따라 달라지며, 객체 수명주기 동안 이 순서가 바쓀 수 이유는 무엇일까?

-> hash값을 이용한 Offset이 같은 값이어서 해시 충동이 나는 경우가 있기 때문에 삽입 순서에 따라 항목의 순서가 달라질 수 있다. 그리고 새로운 key를 집어넣을 때 비어 있는 공간이 부족하면 더 큰 공간이 있는 메모리에 새롭게 hastable을 만들고 데이터를 옮긴다.

 

- 딕셔니리와 집합을 반복하는 동안 항목을 추가하면 왜 안 될까?

-> 위에서 설명한 것처럼 항목을 추가할 때 공간이 부족하면 새로운 hashtable로 옮겨지면서(사용하는 hash결과 의 bit수가 달라질 수 있음.) 순서가 바뀔 수 있다.  시도하면 아래처럼 에러가 발생한다.

a = {i:i for i in range(10)}
for k, v in a.items():
    print(k, v)
    a[k+10] = v + 10
    
0 0
    
 ---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
/var/folders/_k/w0m1fxfx2nngqbf5r4sp65lr0000gn/T/ipykernel_28604/1872387254.py in <module>
----> 1 for k, v in a.items():
      2     print(k, v)
      3     a[k+10] = v + 10

RuntimeError: dictionary changed size during iteration

 

끝으로 hashtable을 사용한 dict는 키 검색이 아주 빠르다. 하지만, 빈 공간을 가지고 있기 때문에 메모리의 오버헤드가 크다는 단점도 있다. 그래서 일정한 key: value형태인데 데이터가 큰 경우는 namedtuple같은 데이터형을 사용하면 효율적이다. 

ex) 많은 양의 JSON Record -> Named Tuple

 

 

지능형 딕셔너리 (dict comprehensions)

# list comprehension 처럼 generator 표현식이 구문으로 dict를 만들 수 있다.
a = {i:i for i in range(10)}

 

매핑 메서드, defaultdict, OrderedDict Class

파이썬의 collections.abc 모듈에서 dict와 유사한 자료형의 인터페이스를 정의하기 위해 Mapping, MutableMapping ABC를 제공.

Or dict나 collections.UserDict를 상속해서 구현하기도 함.

 

dict의 변형 중에 가장 널리 사용되는 데이터객체는 defaultdict와 OrderedDict 클래스이다. 

 

- defaultdict는 default값을 설정할 수 있어서 존재하지 않는 key를 일관성있게 처리할 수 있다.

default_factory 속성과 __missing__(k) 매직 메서드를 구현하여 __getitem__()이 k 키를 찾을 수 없을 때 호출된다.

 

- OrderedDict는 순서 보장이 되지 않는 dict와 달리 순서를 보장해준다. (그렇다고 순서 보장이 필요없는데 OrderedDict를 사용하는 것은 적절하지 않다. 각 데이터형은 목적에 맞게 사용하는 것이 중요.)

 

 

불변 매핑

MappingProxyType이라는 래퍼 클래스를 통해 읽기 전용의 동적 뷰를 만들어서 사용할 수 있다. 

from types import MappingProxyType

d = {'2021': 'I can do it'}
d_proxy = MappingProxyType(d)

print(d_proxy)
{'2021': 'I can do it'}

d_proxy['2022'] = 'let\'s make growth'
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
/var/folders/_k/w0m1fxfx2nngqbf5r4sp65lr0000gn/T/ipykernel_28604/487026469.py in <module>
      1 print(d_proxy)
      2 
----> 3 d_proxy['2022'] = 'let\'s make growth'

TypeError: 'mappingproxy' object does not support item assignment

d['2022'] = 'let\'s make growth'

d_proxy['2022']
"let's make growth"

 

집합 이론

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

 

# 배열을 이용
found = 0
for n in range(1000):
    if n in (1,2,3):
        found += 1

# set의 집합 연산
found = len(set(range(1000)) & set({1,2,3}))

 

마무리

이것으로 3장 정리를 마칩니다. 파이썬에서 가장 자주 사용하는 자료형 중 하나인 dictonary와 또 코드의 가독성과 간결성을 유지할 수 있는 set을 잘 활용해서 개발을 할 수 있도록 의식적으로 노력해봐야 할 것 같습니다. 저의 공부를 위해서 정리한 글이지만 다른 분들도 읽으셨을 때 도움이 되면 좋을 것 같습니다. 

 

 

Reference

- Fluent Python Chapter3