hash(해시) vs trie(트라이)

내가 사용하는 주요 자료구조는 act(array compact trie)이다. 별로 불만 없이 사용하고 있는데 조금더

빠른 방법을 찾던중 해시를  눈에 들어왔다.

요즘과 같이 하드웨어가 좋고 가격이 싸다면 해시를 사용해도 좋을것 같아서

해시와 트라이의 속도를 비교해 보았다.

 

데이터는 약 30만 어절(문자열)이고

트라이로 만들었들때 8.5M정도의 파일로 만들어 지고

해시로 만들었을때는 18M정도가 된다.

 

트라이는 ARRAY 상에서 index를 이동하는 방식으로 구현하였고

해시는 finger print hash function을 사용하여 구현하였다.

우선 입력으로 들어간 문서에 대해 검색시간을 비교하니

해시가 2배가까이 빠른 처리 속도를 보였다.

 

트라이 : 1.4/s

해시 : 0.7/s

 

해시의 버켓 하나당 노드수는 5개정도이다.

 

결론 : 트라이나 해시가 완벽히 옵티마이즈 되지 않았을때는 해시가 좀더 빠르다. 물론 완벽히 옵티마이즈 되도 해시(O(1)가 빠르다.  메모리 걱정만 없다면

 

팁. 참고삼아 리눅스에서 사용하는 버클리 DB는 general 하게 만들어졌기 때문에 다양한 형태의 데이터를 지원할수 있지만 그만큼 속도는 위에 설명한 해시나 트라이에 비해 느리다.