[python] how to implement dict ( hash )
python의 자료구조 중 하나인 dictionary를 어떻게 구현했는지 궁금해서 찾아보다가 아래와 같은 자료를 발견했다.
http://www.laurentluce.com/posts/python-dictionary-implementation/
알고리즘의 기본적 내용은
-
최초 array(bucket)는 8(=2**3)로 시작
-
key값은 python 자체의 hash function을 사용
- 이건 잘 알려진 time hash를 사용해도 될것 같다.
- 새로운 key를 insert하다가 array 사이즈의 2/3이 채워지면 resizing(보통 doubling이라고 한다)
- (4현재 채워진 수)를 계산. 예를 들면, 46 = 24
- 현재 array 사이즈를 1비트씩 shift시키면서 24보다 커지면 정지. 8->16->32
- 즉, 새로운 array 사이즈는 32가 된다.
- 크기가 32인 array를 malloc
- 기존 8사이즈인 array를 32사이즈 array에 insert(re-distribution)
- 기존 8사이즈 array를 free
- collision이 발생하면 quadratic probing 기법을 사용해서 비어있는 slot을 탐색
- 기본적으로는 open addressing 방식이다. close addressing 방식은 hash값으로 찾은 index에 해당하는 cell에 충돌난 값들을 연결시켜주기 때문에 메모리를 많이 사용할 가능성이 있음
probing의 기본적인 알고리즘 :
예를 들어, i=3 ( bucket의 사이즈가 23 이라는 말이다 )
키값을 추가할 경우 j=0부터 시작
j=0에서 collision이 발생할 경우 다음 free slot을 찾는데 아래와 같은 공식을 사용한다.
j = ((5*j) + 1) mod 2i
다음 j = 1
마찬가지로 collision이 발생하면 다음 j = 6
....
0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 -> [repeat]
- 하지만 이 방법은 key값이 무엇이든 매번 같은 순서로 탐색하기 때문에 그렇게 큰 효과를 발휘하기는 어렵다. 이를 해결하기 위해서 아래와 같은 수식을 사용했다.
j = (5*j) + 1 + perturb;
perturb >>= PERTURB_SHIFT;
use j % 2**i as the next table index;
PERTURB_SHIFT 값은 '5'로 정한다.(magic number)
그리고 perturb값은 현재 추가하려고하는 key의 hash값을 사용한다.
이렇게 하면, probing sequence는 key값에 따라 매번 다르게 되고 보다
효율적으로 free slot을 탐색할수 있다는 것.
- key값을 삭제(delete)하는 경우는 resizing하지 않고 dummy slot으로 표시만 한다.
- 또한, dummy slot의 갯수를 기록해둔다.
- 다음번 resizing 연산시 (4* (현재 채워진 수+dummy slot의 수))를 계산해서
이전 array 사이즈를 1비트씩 shift시키면서 위 수를 처음으로 넘어가는 수로 다음 array 사이즈를 잡기 때문에
자동적으로 array 사이즈는 줄어들게 된다.(shirinking)
- key값을 탐색하는 방법은 기본적으로 insert시 free slot을 탐색하는 알고리즘과 동일하다.
- key -> hash -> index
- 해당 index로 접근해서 값이 없으면 진짜 없는 것(bloom filter와 비슷하다. false negative는 항상 참이다.)
-> return false - 해당 index로 접근해서 값이 있으면 해당 값과 key값을 비교연산
동일하면 true positive -> return true
다르면 false positive
만약 다르다면 다른 slot에 존재할수 있기 때문에 그것을 quadratic probing 방식으로(insert에서 사용한 방법과 동일하게) 탐색.
이 방식에 따라, 다음번 위치를 탐색
만약 그 위치가 free slot이면 진짜 없는 것 -> return false
만약 그 위치에 값이 채워져 있으면 해당 값과 key값을 비교연산
....
이런식으로 probing을 하면서 찾는 방식이다.
hash function 자체가 입력 key값을 잘 분산시켜주는 특징도 있고
array(bucket)의 2/3 이상은 채워지지 않기 때문에(resizing, collision이 확률을 줄임)
값을 탐색할때 지나치게 많은 루프를 돌 확률은 줄어들게 된다.
문제는 2/3가 다 채워지지 않은 상태에서 탐색하는 경우인데, 이때가 가장 충돌이 날 확률이 높고
probing도 많이 하게된다.
이런 문제때문에 python에서는 dict에 update() method를 제공한다.
update()는 앞서 insert시 발생하는 resizing과 동일한 방식을 따르기 때문에
dict의 탐색속도를 좀더 빠르게 만들어준다. (key re-distribution)
동료분이 c로 구현한 hash library, 이것의 python c extension, python의 dict를 두고 100만개 정도의 key값을 insert하는 속도를 비교해본 결과
c : 약 1.3초
python c extension : 약 5초
python dict : 약 3.4초
놀라운(?) 부분은 python c extension이 지나치게 느리다는 것이다.
여기 언급된것 처럼 parameter passing, result copy 등의 추가적인 연산이 들어가는 것은 사실이지만 그것이 3배 정도 더 느려지게 만들줄이야.....
확실히 python c extension은 overhead가 존재한다.
python 자체에 이미 잘 구현된 것이 존재하면 그걸 그냥 사용하는 것이 좋을듯~ 만약 없다면 모르겠지만.