第19章：Trie进阶

挑战1：速度有多快？

假设你的新 Swift IDE 有两种自动完成的实现。第一个实现使用一个带有符号的简单字符串数组。第二个实现则使用字符串的 trie。如果符号数据库总共包含1,000,000个条目，并且有四个条目包含由 "prior"、"print"、"priority"、"prius "组成的前缀 "pri "的符号，那么trie的运行速度会快多少？

注：做一个简化的假设，即所有O(1)操作都需要相同的时间，并且n * O(1) == O(n)。

挑战2：附加属性

trie的当前实现缺少一些值得注意的操作。本挑战的任务是通过增加以下内容来增强当前trie的实现。

1. 一个集合属性，返回trie中的所有集合。

2. 告诉你当前在 trie 中有多少个集合的 count 属性。

3. 一个isEmpty属性，如果 trie是空的，返回true，否则返回false。

解决方案

挑战1的解决方案

答案是，字符串的 trie 运行起来 "快得多"。

在这些假设下。

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

1,000,000是数据库大小；3是前缀长度；4是匹配数量；8是条目 "优先级 "的长度。

挑战2的解决方案

你将把集合属性实现为一个存储属性。在Trie.swift中，添加以下新属性。

public private(set) var collections: Set<CollectionType> = []

这个属性是一个Set，将存储Trie中的所有键。

private(set)范围修改器可以防止该属性在类定义之外被篡改。为了使这个Set有用，你需要进一步约束trie，使其持有的集合也是Hashable。

将类的声明更新为以下内容。

接下来，在插入方法中，找到current.isTerminating = true这一行，并将其替换为。

在移除函数中，找到current.isTerminating = false这一行，并在该行下面添加以下内容。

Collections.remove(collection)

添加count和isEmpty属性是直截了当的，因为你已经跟踪了所有的集合。

---

上一章	目录	下一章