19.`Trie`的挑战¶

挑战1：速度有多大？¶

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

Note

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

挑战2：附加属性¶

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

一个collections属性，返回三角形中的所有集合。
一个count属性，告诉你当前在trie中有多少个集合。
一个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是条目priority的长度。

挑战2的解决方案¶

你将实现collections属性作为一个存储属性。在Trie.swift中，添加以下新属性：

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

这个属性是一个Set，它将存储三角形中的所有键。

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

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

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

接下来，在insert方法中，找到current.isTerminating = true一行，将其替换为：

if current.isTerminating {
  return
} else {
  current.isTerminating = true
  collections.insert(collection)
}

在remove函数中，找到current.isTerminating = false一行，在该行下面添加以下内容：

collections.remove(collection)

添加count和isEmpty属性是很简单的，因为你已经跟踪了所有的集合：

public var count: Int {
  collections.count
}

public var isEmpty: Bool {
  collections.isEmpty
}

19.Trie的挑战¶