TRIE에 대하여

내가 지금 사용하고 있는 트라이는 하니가모님이 만드신것이 처음 뿌리이다.

그분에게서 배워와서 약간이 수정(객체 비스므리)을 거쳐 사용하고 있는데

 

공간효율을 위해서 노드간의 포인터를 연결하는 방식을 사용하다보니 본이 아니게 링크드 리스트와 같은 구조가 중간에 생성이 된다.

검색 중간에 검색포인터가 이런 부분에 걸리면 시간이 다른곳에 비해 많이 소비되지만 메모리에서 하는 연산이라 크게 신경을 쓰지 않았었다.

 

그런데 트라이에 들어가는 노드수가 많아지면 많아 질수록 여기에서 허비되는 비용이 만만치 않음을 피부로 느낄수 있었다.

 

요즘 이런 저런 일때문에 트라이 속도 개선을 차일피일 미루던 차에 하니가모님이 트라이 속도 개선에 관한 힌트를 주셔서 짬을 내어 속도 개선작업을 진행하였다.

 

개선 포인트는 두가지이다.

 

 

첫번째는 바이트 연산을 최소화 하기 위해 파일에 바이트단위로 저장하지 않고 unsigned int형으로 한번에 4바이를 저장한다. 이렇게 저장하면 비트 연산과정이 없어진다.

 

두번째는 하니가모님이 힌트를 주신대로 링크드 리스트로 된 부분은 structed array로 만들어 bsearch하는 것이다.

 

그래서 세가지 버전이 나왔다

1. original

2. 비트연산 제거

3. 비트연산 제거 + 링크드 리스트 제거(이진 검색)

 

속도 테스트는 검색시에만 체크한다.

 

입력 데이터 : 3,126,741개의 한글 쿼리

체크 시간은 입력데이터를 모두 찾는데 걸린 시간이다.

 

1. original : 20s

2. 비트연산 제거 : 16s

3. 비트연산 제거 + 링크드 리스트 제거(이진 검색) :  6s

 

메모리에서 연산이 일어난다고 하더라도 그 연산이 몇십만번, 몇백만번 수행한다면

그시간이 결코 작지 않은 것같다.