고성능 파이썬 Chapter 04 - 사전과 셋

이 장에서 배울 내용

- 사전과 셋의 용도

- 사전과 셋의 유사점

- 사전의 오버헤드

- 사전의 성능을 최적화하는 방법

- 파이썬에서 사전을 사용해서 네임스페이스를 유지하는 방법

---

셋과 사전은 특정 데이터를 고유하게 참조할 수 있는 별도 객체가 있는 상황에서 이상적이다. 사전은 key-value로 구성되어있고, 셋은 key값만 존재한다. 이때 key값은 hash가 가능하다면 어떤 타입이어도 상관 없다. 다만 주의해야 할 점은 key값은 유일해야 한다.

셋과 사전은 삽입시의 시간복잡도는 O(1)이고, 탐색시에도 O(1)만에 값을 찾을 수 있다. (이 시간 복잡도는 hash 함수에 종속적인데, hash함수가 value를 균일하게, entropy가 높게, 유지할 수 있을때 O(1)로 동작할 수 있다 - hash 충돌이 생기면 점점 느려진다.)

 

전화번호부를 (이름, 전화번호)의 튜플을 담는 리스트로 구성했다고 가정 했을때, 원하는 이름에 대응되는 전화번호를 찾으려면 순차탐색( 시간복잡도 O(n))을 이용하여 탐색해야 한다. 혹은 정렬하여 O(log n)의 시간복잡도로 탐색할 수 있다.

 

하지만 이런 경우 가장 효율적인 자료구조는 사전(dictionary)이다. 이름을 key로, 전화번호를 value로 하여 값을 저장하면 O(1)의 시간에 원하는 전화번호를 찾을 수 있다.

 

4.1 사전과 셋의 동작 원리

hash table 또한 메모리 상에서 순차적으로 존재한다. 

key에 대응하는 hash값을 modulo 계산을 통해 배열의 index를 계산할 수 있다. ( 시간 복잡도 O(1)) 

해당 메모리 블록이 사용 중인지 검사하고, 사용하고 있지 않다면 값을 저장한다.

만약 사용중이면, 저장된 값과 value와 동일한지 비교하고, 다르다면 hash 충돌이 일어난 경우이다. 데이터를 저장할 다른 위치를 찾아야 한다. 실제의 동작 원리는 key-value를 배열에 append하고, 이 배열의 index를 해시 테이블에 저장한다고 한다. (따라서 이 배열의 순서가 hash가 저장된 순서)

데이터 삽입 도중 충돌이 발생한 테이블의 동작

프로빙

해시 값이 충돌이 되었을때, 다른 값을 시도해 보는 것. 파이썬은 원래 해시 값에서 더 상위 bit을 이용하여 다음 위치를 찾음.

dict_proving.py

 

로트펙터

해시 테이블에 데이터가 얼마나 균등하게 분포하는지.  (해시 함수의 엔트로피와 관련)

삭제

해시 테이블에서 값을 제거할때 단순히 메모리 블럭을 NULL로 바꾸면 안됨. (NULL은 해시 충돌을 위한 감시값으로 사용 중). 블록이 비었음을 의미하는 특수 값이 존재하여 이 값을 씀. 위의 그림에서 Rome을 제거한 뒤, Barcelona를 검색하면 Rome이 있던 위치로 간 후 프로빙을 통해 검색됨.

크기 변경

해시에서 값을 추가하게되면, 테이블의 크기도 언젠간 조정되야 한다. 파이썬에서는 2/3이 채워지면 크기를 3배로 늘리게 된다.

--> 처음 딕셔너리에 값이 3개 저장되어있을때 해시 테이블은 8의 크기를 갖는다. (최소 크기인 경우), 8의 2/3인 6번째 값이 딕셔너리에 저장될때  6의 3배인 18의 크기로 해시 테이블의 크기가 조정된다.

반대로 딕셔너리에서 많은 값을 제거하면 해시 테이블의 크기도 줄어들게 된다. 하지만 실질적인 크기 변경은 삽입 연산 중에만 발생한다.
--> 여러 값을 지우고 다음 삽입을 할때 크기 변경이 이루어진다.

 

해시 함수와 엔트로피

파이썬은 object는 __hash__, __cmp__ 함수를 구현하므로 해시가 가능하다. int, float는 bit를 기반으로 해싱하고, 문자열은 내용을 가지고 해싱한다. list는 그 값이 변할 수 있기 때문에 해시를 지원하지 않는다. 객체는 메모리의 주소를 가지고 해싱을 한다.

 

동일한 값을 가지는 (x,y) 객체를 여러개 만들때 일반적으로 다른 객체로 인식해서 각각의 항목이 추가가 될 것이다. 하지만, object의 내용을 기반으로 해싱을 하고 싶으면 __hash__, __cmp__ 함수를 정의하면 동일한 해시값을 반환하여 동일하게 인식 될 것이다.

 

해싱을 할때 해시 값이 균일하게 분포되도록 신경써야 한다. 해시 충돌이 발생하면 계속해서 프로빙을 해야 하므로 성능에 악영향을 미칠 수 있기 때문이다. 최약의 경우 O(n)의 시간 복잡도를 갖는다.

 

사용자 정의 해시

위 GoodHash해시 함수는 두 영어 알파벳 소문자를 조합하였을때 최적인 해시 함수이다.

BadHash는 무조건 해시 충돌을 겪게 되고, GoodHash는 해시 충돌이 발생하지 않는다.

해시 함수에 따라 80배의 성능 차이를 보여준다.

 

4.2 사전과 네임스페이스

파이썬에서 변수, 함수, 모듈이 사용될 때 그 객체를 어디서 찾을지 결정하는 계층은

locals() -> globals() -> __builtin__ 순이다.

locals, globals는 사전으로 관리되고, __builtin__은 모듈 객체이다. 즉, __builtin__ 영역까지 가게되면 속도가 조금이나마 느려진다.

따라서 명시적으로 함수를 호출하는것이 속도를 빠르게 해준다.