Chapter 19: Trie Challenges

Challenge 1: How much faster?

자동 완성(autocomplete) 기능을 구현한다고 가정한다. 첫 번째 구현에는 간단한 문자열(string) 배열(Array)를 사용하고, 두 번째 구현에는 Trie를 사용한다. 데이터베이스에 총 100,000 개의 항목이 있고, "pri" 접두사(prefix)를 가진 4개의 항목 "prior", "print", "priority", "prius"이 포함되어 있을 경우, trie가 array에 비해 얼마다 더 빠른지 확인한다.

모든 O(1) 연산은 동일한 시간이 걸린다 가정한다. 따라서 n * O(1) == O(n) 이다.

 

Solution

Trie가 훨씬 빠르게 실행된다. 대략적인 추정 시간은 다음과 같다.

1,000,000 * 3 * O(1) / 4 * 8 * O(1) = 93,750 times faster

여기서 1,000,000는 데이터베이스 크기이다. 3의 접두사(prefix)의 길이, 4는 일치 횟수, 8은 "priority" 항목의 길이이다.

---

Challenge 2: Additional properties

유용하게 사용할 수 있는 추가적인 속성을 Trie에 구현한다.

1. collections : trie의 모든 collection을 반환한다.
2. count : 현재 trie의 collection 수를 반환한다.
3. isEmpty : trie가 비어 있는지 여부를 반환한다.

 

Solution

Trie 클래스에 추가적인 속성을 구현한다.

public private(set) var collections: Set<CollectionType> = [] 
//stored property로 구현

이 속성은 모든 key를 Trie에 저장하는 집합(Set)이다. get은 public 이고, set은 private으로, 해당 속성이 클래스 정의 외부에서 변경되는 것을 막는다. 이 Set를 사용하려면, Collection이 Hashable을 구현하도록 제한해야 한다. 클래스 선언을 업데이트 한다.

 public class Trie<CollectionType: Collection & Hashable> where CollectionType.Element: Hashable

다음으로, insert 메서드에서 current.isTerminating = true를 다음과 같이 변경한다.

public func insert(_ collection: CollectionType) {
    var current = root
    for element in collection {
        if current.children[element] == nil {
            current.children[element] = Node(key: element, parent: current)
        }
        current = current.children[element]!
    }
    
//    current.isTerminating = true
    //수정
    if current.isTerminating {
        return
    } else {
        current.isTerminating = true
        collections.insert(collection)
    }
}

remove 메서드의 current.isTerminating = false의 다음 부분도 변경해 준다.

public func remove(_ collection: CollectionType) {
    var current = root
    for element in collection {
        guard let child = current.children[element] else {
            return
        }
        
        current = child
    }
    
    guard current.isTerminating else {
        return
    }
  
    current.isTerminating = false
    collections.remove(collection) //추가
    
    while let parent = current.parent, current.children.isEmpty && !current.isTerminating {
        parent.children[current.key!] = nil
        current = parent
    }
}

count와 isEmpty 속성도 간단히 구현할 수 있다.

public var count: Int {
    collections.count
}
    
public var isEmpty: Bool {
    collections.isEmpty
}