几乎地球上的每个程序都必须以这样或那样的方式处理字符串，因为文本对于我们如何通信和表示各种形式的数据是如此重要。但是，以一种既健壮又高效的方式处理和解析字符串有时会非常困难。虽然有些字符串以非常严格和计算机友好的格式出现，如JSON或XML，但其他字符串可能要混乱得多。
这周，让我们看看从这些字符串中解析和提取信息的各种方法，以及不同的技术和api如何产生不同的权衡。
String and its friends
在某些方面，Swift因其在字符串解析方面有点难处理而声名鹊起。虽然Swift的字符串实现并没有像其他语言那样提供那么多的便利(例如，你不能简单地使用整数访问给定的字符，比如字符串[7])，它确实使编写正确的字符串解析代码变得更容易。
因为尽管能够根据感知到的位置随机访问字符串中的任何给定字符是件好事，但我们今天生活的多语言(或者可能是表情符号语言?)的世界使这种api非常容易出错，因为在很多情况下，在文本UI中表示字符的方式与在字符串值中存储字符的方式非常不同。
在Swift中，字符串由一组使用UTF-8编码存储的字符值组成。 这意味着如果我们遍历一个字符串(例如使用for循环)，每个元素都将是一个字符——可能是一个字母、一个表情符号或其他形式的字符。要识别一组字符(如字母或数字)，我们可以使用字符集，它可以传递给关于字符串及其相关类型的几个不同的api。
Tokenizing usernames
假设我们正在开发一个应用程序，让几个不同的用户在一个文档上协作，我们想实现一个功能，让用户使用类似twitter的@mention语法来提及其他人。
识别给定字符串中提到的用户实际上与Swift编译器在识别代码字符串中的不同部分时所需要做的工作非常相似 —称为词法分析或标记化的过程—只是我们的实现要简单几个数量级，因为我们只需要寻找一种标记。
初始实现可能是这样的——String上的一个计算属性，在这个属性中，我们根据@字符分割字符串，删除第一个元素(因为它将是第一个@-符号之前的文本)，然后对结果进行compactMap—— 识别非空的纯字母字符字符串：
extension String {
var mentionedUsernames: [String] {
let parts = split(separator: "@").dropFirst()
// Character sets may be inverted to identify all
// characters that are *not* a member of the set.
let delimiterSet = CharacterSet.letters.inverted
return parts.compactMap { part in
// Here we grab the first sequence of letters right
// after the @-sign, and check that it’s non-empty.
let name = part.components(separatedBy: delimiterSet)[0]
return name.isEmpty ? nil : name
}
}
}
上面的实现非常简单，并且使用了一些非常好的Swift特性——比如修改集合，使用compactMap丢弃nil值，等等。但它确实有一个问题——它需要三次迭代，一次基于@字符分割字符串，一次遍历所有这些部分，然后一次基于非字母字符分割每个部分。
虽然每次迭代都小于前一次迭代(所以我们的算法的复杂度不是O(3N))， 随着输入数据集的增长，多次迭代通常会导致某种形式的瓶颈。 这在我们的例子中可能成为一个问题，因为我们正计划将此算法应用于任何大小的文档(也许有些用户会用我们的应用一起写一本书，谁知道呢?)我们来看看能不能做点什么来优化它。
与其将字符串分割成组件，然后遍历这些组件，不如通过遍历字符串中的字符来进行一次遍历。 虽然这需要更多的手动解析代码，但它将使我们能够将算法简化为一次迭代——像这样:
extension String {
var mentionedUsernames: [String] {
// Setting up our state, which is any partial name that we’re
// currently parsing, and an array of all names found.
var partialName: String?
var names = [String]()
// A nested parsing function, that we’ll apply to each
// character within the string.
func parse(_ character: Character) {
if var name = partialName {
guard character.isLetter else {
// If we encounter a non-letter character
// while parsing a name, it means that the
// name is finished, and we can add it to
// our array (if non-empty):
if !name.isEmpty {
names.append(name)
}
// Reset our state, and parse the character
// again, since it might be an @-sign.
partialName = nil
return parse(character)
}
name.append(character)
partialName = name
} else if character == "@" {
// Set an empty state, to signal to our above
// code that it’s time to start parsing a name.
partialName = ""
}
}
// Apply our parsing function to each character
forEach(parse)
// Once we’ve reached the end, we’ll make sure to
// capture any name that was previously found.
if let lastName = partialName, !lastName.isEmpty {
names.append(lastName)
}
return names
}
}
注意，上面的isLetter API是在Swift 5中添加的。
虽然上面的实现比我们最初的要复杂得多——它的速度(平均)是原来的两倍，这给了我们第一个明确的权衡: 我们是选择以潜在的性能成本为代价的更简单的解决方案，还是选择维护一个更复杂、更高效的算法?
Detecting multiple tokens
随着需求列表的增长，讨论接受哪一种取舍变得更加有趣。假设在成功地向用户推出了提及功能后，我们开始收到添加对标签支持的请求，我们决定这样做。
因为检测用户名和标签是完全相同的问题(只是开头字符不同- @ vs #)，使用相同的实现来检测两者是有意义的。为了实现这一点，让我们首先定义一个符号类型，我们将用它来表示一个提及或一个标签:
struct Symbol {
enum Kind { case mention, hashtag }
let kind: Kind
var string: String
}
而我们可以使用带有关联字符串值的枚举代替 -由于提到和标签共享相同的结构，使用结构会使我们的算法更简单一些。 然而，为了使Symbol能够以类似枚举的方式使用，我们还可以添加一些静态工厂方法，使使用点语法构造值变得更容易:
extension Symbol {
static func mention(_ string: String) -> Symbol {
return Symbol(kind: .mention, string: string)
}
static func hashtag(_ string: String) -> Symbol {
return Symbol(kind: .hashtag, string: string)
}
}
有了上面的内容，现在让我们更新之前提到的usernames算法来检测符号，而不仅仅是用户名:
extension String {
var symbols: [Symbol] {
var partialSymbol: Symbol?
var symbols = [Symbol]()
func parse(_ character: Character) {
if var symbol = partialSymbol {
guard character.isLetter else {
if !symbol.string.isEmpty {
symbols.append(symbol)
}
partialSymbol = nil
return parse(character)
}
symbol.string.append(character)
partialSymbol = symbol
} else {
// Here’s the only real difference compared to
// the previous version, since we’ll now decide
// what kind of symbol we’re parsing based on
// its leading character:
switch character {
case "@":
partialSymbol = .mention("")
case "#":
partialSymbol = .hashtag("")
default:
break
}
}
}
forEach(parse)
if let lastSymbol = partialSymbol, !lastSymbol.string.isEmpty {
symbols.append(lastSymbol)
}
return symbols
}
}
通过上面的改变，我们最初基于字符串分割的实现和我们最新算法之间的差异变得更大了——因为如果我们通过分割字符串来标记用户名和标签，我们需要6个不同的迭代(2倍3) -两个完整的字符串将通过原始字符串。
然而，如果我们能在初始实现的简单性和手动算法的强大性之间找到某种中间地带，那就太好了。一种方法是引入一种抽象，将算法的标记化部分与实际处理任何发现的标记的逻辑分开。
为了做到这一点，让我们将最新算法的大部分移动到一个tokenize方法中，该方法接受一个处理程序的字典，基于它们处理的字符进行散列——像这样:
xtension String {
func tokenize(using handlers: [Character : (String) -> Void]) {
// We no longer have to maintain an array of symbols,
// but we do need to keep track of both any currently
// parsed symbol, as well as which handler its for.
var parsingData: (symbol: String, handler: (String) -> Void)?
func parse(_ character: Character) {
if var data = parsingData {
guard character.isLetter else {
if !data.symbol.isEmpty {
data.handler(data.symbol)
}
parsingData = nil
return parse(character)
}
data.symbol.append(character)
parsingData = data
} else {
// If we have a handler for a given character,
// then we’ll parse it.
guard let handler = handlers[character] else {
return
}
parsingData = ("", handler)
}
}
forEach(parse)
if let lastData = parsingData, !lastData.symbol.isEmpty {
lastData.handler(lastData.symbol)
}
}
}
上面的方法不仅使我们的实现更清晰，而且给了我们更多的灵活性 - 因为我们现在可以在许多不同的上下文中重用相同的标记化算法，并选择每个标记应该如何在调用站点处理。
我们现在可以减少我们的符号解析代码，从以前到现在:
extension String {
var symbols: [Symbol] {
var symbols = [Symbol]()
tokenize(using: [
"@": { symbols.append(.mention($0)) },
"#": { symbols.append(.hashtag($0)) }
])
return symbols
}
}
非常漂亮和干净!👍但是，就像以前一样，这涉及到一系列的权衡。 虽然抽象是一种将复杂逻辑隐藏在更好的API背后的好方法——但它们并不是免费的。事实上，与将算法内联到symbols属性时相比，我们的最新版本需要更多40%的时间来运行。然而，它仍然是用分裂字符串来做同样事情的两倍，所以它可能是我们想要的中间位置。
Scanning for tokens
到目前为止，我们主要比较的是手动遍历字符串的字符和将其拆分为组件——但是，就像许多其他事情一样，还有更多的选项需要考虑。
其中一个选项是使用Foundation的扫描器类型来持续扫描字符串，以识别我们正在寻找的令牌。 就像我们之前的最后一个实现一样，它让我们能够依靠抽象(这一次是苹果提供的)来处理我们算法的大部分“繁重工作”。这样的实现应该是这样的:
extension String {
var symbols: [Symbol] {
let scanner = Scanner(string: self)
let symbolSet = CharacterSet(charactersIn: "@#")
var symbols = [Symbol]()
var symbolKind: Symbol.Kind?
// Scanner doesn’t expose a sequence-like API, but rather
// requires us to inspect its current state to decide
// when the iteration is over.
while !scanner.isAtEnd {
if let kind = symbolKind {
symbolKind = nil
// Since Scanner is actually just a Swift interface
// to the NSScanner Objective-C class, it requires
// us to pass it an NSString pointer, which it’ll
// write the result into.
var result: NSString?
scanner.scanCharacters(from: .letters, into: &result)
guard let string = result else {
continue
}
symbols.append(Symbol(kind: kind, string: string as String))
} else {
// Here we scan until we’ve found either an @ or
// a # character, and then consume that character
// while assigning a symbol kind to parse.
scanner.scanUpToCharacters(from: symbolSet, into: nil)
if scanner.scanString("@", into: nil) {
symbolKind = .mention
} else if scanner.scanString("#", into: nil) {
symbolKind = .hashtag
}
}
}
return symbols
}
}
然Scanner的“Objective-C-ness”可能会让我们的代码看起来不那么“敏捷”，但对于这类问题，它是一个有效的选项-它的性能特征与我们之前的基于迭代的手工实现不相上下。也可以认为，使用Scanner生成的代码可读性稍微强一些，因为它的api显式地声明，我们正在扫描算法的每个部分中的给定字符串，但这是非常主观的。
The art of being lazy
让我们看一看优化的最后一种方式——使用惰性集合。到目前为止，我们所探讨的所有实现都有一个共同点——它们都能立即解析整个字符串。虽然这对于将立即使用所有结果的用例来说是完全没问题的，但是我们可以通过以一种更懒惰的方式执行解析来潜在地进一步优化。
就像我们在“Swift序列:懒惰的艺术”中看到的那样，延迟计算序列中的一个元素，直到它真正需要时，有时可以提高我们的性能——尤其是当调用者只使用我们序列的一个子集时。
让我们将最后一个基于扫描器的实现更新为延迟执行。为此，我们将算法封装在AnySequence和AnyIterator中，这使我们能够形成惰性序列，而无需从头实现一个新类型:
extension String {
var symbols: AnySequence<Symbol> {
// Since our character set is a constant, we can compute
// it immediately, outside of our iteration closure.
let symbolSet = CharacterSet(charactersIn: "@#")
// AnySequence enables us to use closures to define both
// our sequence and its underlying iterator.
return AnySequence<Symbol> { () -> AnyIterator<Symbol> in
let scanner = Scanner(string: self)
var symbolKind: Symbol.Kind?
// We’ve refactored our algorithm a bit to instead
// use a nested function, that will be called by the
// iterator to retrieve the next element (or nil, once
// we’ve reached the end of the sequence).
func iterate() -> Symbol? {
guard !scanner.isAtEnd else {
return nil
}
guard let kind = symbolKind else {
scanner.scanUpToCharacters(from: symbolSet, into: nil)
if scanner.scanString("@", into: nil) {
symbolKind = .mention
} else if scanner.scanString("#", into: nil) {
symbolKind = .hashtag
}
return iterate()
}
symbolKind = nil
var result: NSString?
scanner.scanCharacters(from: .letters, into: &result)
guard let string = result else {
return iterate()
}
return Symbol(kind: kind, string: string as String)
}
return AnyIterator(iterate)
}
}
}
通过上面的改变，我们现在将得到相当显著的性能提升的代码，像这样的代码，只迭代我们的符号序列，直到给定的点:
let firstHashtag = string.symbols.first { $0.kind == .hashtag }
这就为我们呈现了本文的最终取舍——我们是否愿意接受额外的一点复杂性(以及可能稍微困难一点的调试)，以使更短的迭代具有更好的性能?
Conclusion
就像在编写任何一种算法时，到底哪种实现最合适，很大程度上取决于我们要处理的问题类型、我们计划运行它的数据集有多大，以及结果将如何被使用。
当然，还有许多本文没有介绍的其他方法来解析Swift中的字符串-例如使用正则表达式，或者深入到底层Unicode级别上解析内容-但希望它能让你对我们使用的一些工具和技术有一个概述，以及各种各样的权衡。
我个人的方法几乎总是从最简单的实现开始，同时不断地测量算法的结果和性能特征，根据需要进行扩展——就像本文中一样。在下一篇文章中，我们还将更仔细地研究如何根据各种性能指标准确地度量代码。