第七章——字符串(字符串性能)

151 阅读3分钟

本文系阅读阅读原章节后总结概括得出。由于需要我进行一定的概括提炼,如有不当之处欢迎读者斧正。如果你对内容有任何疑问,欢迎共同交流讨论。

毫无疑问,把多个UTF-16编码的代码点合并成一个字形集群比直接处理这些代码点更耗时。本节,我们用之前实现的正则表达式匹配器处理不同的字符串视图,具体的展示在不同视图下性能的差异。

我们需要对此前的Regex做一些改进,因为它当时仅使用了CharacterView视图。为了测试不同视图下的性能差异,我们需要让它支持另外三个视图UTF8ViewUTF16ViewUnicodeScalarView

根据面向协议编程的思想,你可能会实现一个范型的Regex结构体,并且提供一个占位类型(这通常是一个协议)。但问题在于没有一个公共的协议同时被这四种视图实现。另一个问题是,在匹配过程中,我们需要把字符常量"*""^"等,和正则表达式进行比较。在不同的视图下,这些字符串常量也需要有不同的表达形式。

最后一个问题是,我们希望正则表达式的初始化函数的参数依然是String类型,那么它怎么知道在内部应该选择哪个视图呢?

一种技术是把所有会变化的逻辑封装到一个单独的类型中,并且把它作为匹配器的一个参数,首先我们定义一个通用的协议:

protocol StringViewSelector {
typealias ViewType: CollectionType

static var carit:       ViewType.Generator.Element { get }
static var asterisk:    ViewType.Generator.Element { get }
static var period:      ViewType.Generator.Element { get }
static var dollar:      ViewType.Generator.Element { get }

static func viewFrom(s: String) -> ViewType
}

这个协议中包含了一个类型别名,表示我们要用的视图类型,以及需要用到的四个常量,还有一个viewFrom函数用于提取参数字符串的对应视图。这么说可能有些抽象,我们看两个实现:

struct CharacterViewSelector: StringViewSelector {
static var carit:       Character { return "^" }
static var asterisk:    Character { return "*" }
static var period:      Character { return "." }
static var dollar:      Character { return "$" }

static func viewFrom(s: String) -> String.CharacterView { return s.characters }
}

struct UTF8ViewSelector: StringViewSelector {
static var carit:       UInt8 { return UInt8(ascii: "^") }
static var asterisk:    UInt8 { return UInt8(ascii: "*") }
static var period:      UInt8 { return UInt8(ascii: ".") }
static var dollar:      UInt8 { return UInt8(ascii: "$") }

static func viewFrom(s: String) -> String.UTF8View { return s.utf8 }
}

剩下的UTF16ViewSelectorUnicodeScalarViewSelector结构体的实现就不写了,估计你也能猜到。

这就是我们所说的虚类型(Phantom Type),这种类型实际上不会存储任何数据,因此调用sizeof(CharacterViewSelector)得到的结果是0。我们使用这样的类型,让Regex结构体的逻辑参数化,也就是说随着StringViewSelector类型的不同,Regex结构体的逻辑也不同:

struct Regex<V: StringViewSelector
where V.ViewType.Generator.Element: Equatable,V.ViewType.SubSequence == V.ViewType> {
let regexp: String

init(_ regexp: String) {
self.regexp = regexp
}

func match(text: String) -> Bool {
let text = V.viewFrom(text)
let regexp = V.viewFrom(self.regexp)
//如果regex以^开头,只能从参数的第一个字符开始匹配
if regexp.first == V.carit {
return Regex.matchHere(regexp.dropFirst(), text)
}

//依次从不同的位置开始,尝试匹配每一个子串
for var idx = text.startIndex; ; ++idx {
if Regex.matchHere(regexp, text[idx..<text.endIndex]) {
return true
}
if idx == text.endIndex { break }
}

return false
}

static func matchHere(regexp: V.ViewType, _ text: V.ViewType) -> Bool {
// 以下省略具体的匹配逻辑
return true
}
}

重写了Regex结构体后,性能测试的函数就很容易实现了:

func benchmark<V: StringViewSelector
where V.ViewType.Generator.Element: Equatable,
V.ViewType.SubSequence == V.ViewType>
(_: V.Type) {
let r = Regex<V>("h..a*")
var count = 0

let startTime = CFAbsoluteTimeGetCurrent()
while let line = readLine() {
if r.match(line) { count = count &+ 1 }
}
let totalTime = CFAbsoluteTimeGetCurrent() - startTime
print("\(V.self): \(totalTime)")
}

func ~=<T: Equatable>(lhs: T, rhs: T?) -> Bool {
return lhs == rhs
}

switch Process.arguments.last {
case "ch": benchmark(CharacterViewSelector.self)
case "8": benchmark(UTF8ViewSelector.self)
case "16": benchmark(UTF16ViewSelector.self)
case "sc": benchmark(UnicodeScalarViewSelector.self)
default: print("Unrecognized view type")
}

如果选择一段很长的文本(12.8万行,一百万个单词),我们得到如下的输出结果:

UTF160.31 seconds
UnicodeScalar0.77 seconds
UTF81.7 seconds
Characters10 seconds

可见,UTF16编码下的性能最高,Characters视图的性能远低于另外三个。