트라이(Trie)와 자바 패키지

※ 알림: 이 글은 트라이(Trie)로 자바 패키지 검색 시스템을 구현하는 것을 목적으로 두고 있습니다. 또 왜 트라이로 검색 시스템을 구축할 수 없는지를 다른 자료구조와 함께 실험을 통해 증명합니다.

 

[사전 지식]

  기본적으로 자바 패키지는 디렉토리 구조를 가진다. 실제로 자바 프로젝트를 생성해서 패키지를 생성하면 점(.)를 기준으로 디렉토리가 생성되고 그러한 파일 시스템을 가진다.

파일 시스템과 패키지 구조

[상황]

  각 패키지와 그 패키지에 속한 클래스들을 관리해야 한다.

 

  이제 위 데이터를 접근하기 위해서는 먼저 정의된 패키지에 접근하여 클래스 객체에 접근할 필요가 있다. 패키지에 접근하려면 가장 적합한 자료구조는 무엇일까? 여기서 크게 세 가지 자료구조를 확인하고 성능을 체크하고자 한다.

 

[후보 1] 파일 시스템처럼 리스트로 관리한다.

  가장 쉽고 간단한 자료구조. 하위 클래스 또는 패키지가 있고 그 클래스와 패키지들을 배열 형식으로 관리한다. 일반적으로 패키지 구조 자체가 변경되지 않기 때문에 정해진 배열 크기로 잡아도 상관없다. 단점이 있다면 특정 클래스 또는 패키지를 검색할 때 시간이 오래 걸린다. 정렬되어 있다면 이분탐색으로 O(lgN)까지 가능하다.

  예상되는 시간 복잡도: O(NlgN)

  예상되는 공간 복잡도: O(N)

 

[후보 2] 패키지 경로를 Key로 두고 Value를 클래스 리스트로 두는 HashMap으로 관리한다.

  [후보 1]에서 조금 발전한 형태. 클래스 또는 패키지 검색할 때 보다 빠른 속도로 접근할 수 있다. 가령 클래스org.a.b.c.TestClass의 경우 key는 "org.a.b.c"이고 value는 ["TestClass"]가 된다.

  예상되는 시간 복잡도: O(hash function)

  예상되는 공간 복잡도: O(N)

 

[후보 3] 트라이(Trie) 구조로 관리한다. 각 노드는 패키지의 구분자 역할이다.

  이 구조에서는 모든 패키지와 클래스에 대해서 경로를 구분하는 점(.) 단위로 나눠서 노드를 설정한다. 가령 클래스org.a.b.c.TestClass의 경우 노드는 총 4개가 된다. 마지막 TestClass는 패키지 경로가 아닌 클래스이므로 제외한다. 노드를 검색할 때는 해시 자료구조를 이용한다. 

  예상되는 시간 복잡도: O(N * (hash function))

  예상되는 공간 복잡도: O(N)

 

  눈에 보이듯 당연히 [후보 2]가 더 빠르다. 하지만 클래스, 패키지가 많아지면 hash collision으로 인해 속도가 느려지고 그로 인해 [후보 3]이 더 빠른 속도를 가지지 않을까 생각했다.

 

  - 실험 테스트 셋 : "여기"서 다운 받으시면 된다.

  - 실험 내용

    후보2와 후보3을 구현하고 성능테스트를 진행한다. 위 자료구조에서는 검색이 빨라야하므로 쿼리를 변경해가며 테스트한다.

  - 실험 방법

    - 패키지 수 : 500, 1000, 3000, 5000, 8000, 10000, 30000, 50000, 80000, 100000, 300000, 500000개로 두고 변경하며 테스트한다.

    - 쿼리 수 : 모든 패키지를 찾아본다. 즉, 쿼리의 수는 입력으로 주어진 패키지 수가 된다.

  - 실험 결과

    실험 결과 아래와 같이 표로 나타낼 수 있다. 단위는 초(second)다.

 

표1 - 패키지 수에 따른 쿼리에 걸린 시간

그래프1 - 표1을 그래프로 나타내면 위와 같다

 

[결론]

  어느 구간에서도 후보3이 후보2보다 빠른 곳이 없다. 따라서 특정 구분자를 가지고 있는 입력(Java 패키지 경로 같은)에 대해 굳이 트라이를 쓰지 말고 Hash+set을 사용하여 시스템을 만들자.