如何高效地在Swift中比较字符

Question

我有一个用Swift编写的函数，它计算两个字符串的汉明距离，如果结果为1，则将它们放入一个连接图中。

例如，从“read”到“hear”的汉明距离为2，因为“read [0]！= hear [0]”和“read [3]！= hear [3]”。

起初，我认为我的函数由于输入量太大（8,000+字典），所以需要很长时间，但是几分钟显然太长了。因此，我用Java重写了相同的算法，计算仅花费了0.3秒。

我尝试用Swift的两种不同方式编写此代码：

---

方式1 - 子字符串

extension String {

    subscript (i: Int) -> String {
        return self[Range(i ..< i + 1)]
    }

}

private func getHammingDistance(w1: String, w2: String) -> Int {
    if w1.length != w2.length { return -1 }

    var counter = 0
    for i in 0 ..< w1.length {
        if w1[i] != w2[i] { counter += 1 }
    }

    return counter
}

结果: 434 秒钟

---

方法二 - 删除字符

private func getHammingDistance(w1: String, w2: String) -> Int {
    if w1.length != w2.length { return -1 }

    var counter = 0
    var c1 = w1, c2 = w2      // need to mutate
    let length = w1.length

    for i in 0 ..< length {
        if c1.removeFirst() != c2.removeFirst() { counter += 1 }
    }

    return counter
}

结果: 156秒

---

Java中相同的事情

结果: 0.3秒

---

调用位置

var graph: Graph

func connectData() {
    let verticies = graph.canvas // canvas is Array<Node>
                                 // Node has key that holds the String

    for vertex in 0 ..< verticies.count {
        for compare in vertex + 1 ..< verticies.count {
            if getHammingDistance(w1: verticies[vertex].key!, w2: verticies[compare].key!) == 1 {
                graph.addEdge(source: verticies[vertex], neighbor: verticies[compare])
            }
        }
    }
}

---

对我来说，156秒仍然过于低效。在Swift中比较字符的绝对最有效方法是什么？是否存在一种计算汉明距离的可能解决方案，其中不涉及比较字符？

---

编辑

编辑1: 我正在取一个包含4和5个字母的完整字典，并创建一个连接图，其中边表示汉明距离为1。因此，我将8,000多个单词相互比较以生成边缘。

编辑2: 添加方法调用。

- Logan Jahnke

---

“方式2”比“方式1”更快似乎非常奇怪。为什么修改字符串会更快呢？看看是否可以像在“方式2”中使用“length”变量一样，在“方式1”中使用它来提高速度。 - rmaddy

@LoganJahnke 在Swift 3中，字符串没有采用整数下标的原因是，在Swift字符串的Unicode正确性情况下，无法通过索引进行常量时间访问。你编写的那个扩展会对整个字符串进行线性扫描。请参见https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/StringsAndCharacters.html#//apple_ref/doc/uid/TP40014097-CH7-ID301。 - Alexander

如果您更新问题并提供调用getHammingDistance方法的代码，将有助于其他人更好地理解问题。显然，您已经多次调用了该方法。 - rmaddy

好的，你有多少个比较？8500 * 8500？ - Bence Pattogato

这个稍微少一点。我在 O(n^2 / 2) 中。结果是8500 * 4250。 - Logan Jahnke

Answer 1

除非您为字符串选择了固定长度字符模型，否则 .count 和 .characters 等方法和属性的复杂性将为 O(n) 或最多为 O(n/2)（其中 n 是字符串长度）。如果您将数据存储在字符数组中（例如 [Character] ），则函数的性能将大大提高。

您还可以使用 zip() 函数将整个计算组合成单个传递。

let hammingDistance = zip(word1.characters,word2.characters)
                      .filter{$0 != $1}.count 

但这仍然需要遍历每个单词对的所有字符。

...

考虑到你只寻找汉明距离为1的情况，有一种更快的方法来获取所有唯一的单词对：

策略是按照对应一个“缺失”字母的4（或5）种模式将单词分组。每个模式组定义了较小的单词对范围，因为不同组中的单词之间的距离不会是1。

每个单词都会属于其字符计数所在的多个组。

例如：

"hear" will be part of the pattern groups:
"*ear", "h*ar", "he*r" and "hea*".

与这四个模式组中任何一个对应的单词都与"hear"的汉明距离为1。

下面是如何实现它的：

// Test data 8500 words of 4-5 characters ...
var seenWords = Set<String>()
var allWords = try! String(contentsOfFile: "/usr/share/dict/words")
                     .lowercased()                        
                     .components(separatedBy:"\n")
                     .filter{$0.characters.count == 4 || $0.characters.count == 5}
                     .filter{seenWords.insert($0).inserted}
                     .enumerated().filter{$0.0 < 8500}.map{$1}

// Compute patterns for a Hamming distance of 1
// Replace each letter position with "*" to create patterns of
// one "non-matching" letter
public func wordH1Patterns(_ aWord:String) -> [String]
{
   var result       : [String]    = []
   let fullWord     : [Character] = aWord.characters.map{$0}
   for index in 0..<fullWord.count
   {
      var pattern    = fullWord
      pattern[index] = "*" 
      result.append(String(pattern))                     
   }
   return result
}

// Group words around matching patterns
// and add unique pairs from each group
func addHamming1Edges()
{
   // Prepare pattern groups ...
   // 
   var patternIndex:[String:Int] = [:]
   var hamming1Groups:[[String]]  = []
   for word in allWords
   {
      for pattern in wordH1Patterns(word)
      {
         if let index = patternIndex[pattern]
         { 
           hamming1Groups[index].append(word) 
         }
         else
         {
           let index = hamming1Groups.count
           patternIndex[pattern] = index
           hamming1Groups.append([word])
         }        
      }
   }

   // add edge nodes ...
   //
   for h1Group in hamming1Groups
   {
       for (index,sourceWord) in h1Group.dropLast(1).enumerated()
       {
          for targetIndex in index+1..<h1Group.count
          { addEdge(source:sourceWord, neighbour:h1Group[targetIndex]) } 
       }
   }
}

在我的2012年款MacBook Pro上，8500个单词在0.12秒内经过了22817个（独特的）边缘对。[编辑]为了说明我之前的观点，我使用了字符数组而不是字符串来创建了一个“蛮力”算法：

   let wordArrays = allWords.map{Array($0.unicodeScalars)}
   for i in 0..<wordArrays.count-1
   {
      let word1 = wordArrays[i]
      for j in i+1..<wordArrays.count
      {
         let word2 = wordArrays[j]
         if word1.count != word2.count { continue }

         var distance = 0
         for c in 0..<word1.count 
         {
            if word1[c] == word2[c] { continue }
            distance += 1
            if distance > 1 { break }
         }
         if distance == 1
         { addEdge(source:allWords[i], neighbour:allWords[j]) }
      }
   }

这个程序在0.27秒内遍历了所有唯一的pairs。速度差异的原因在于Swift Strings内部模型不是等长度元素（字符）的数组，而是一个由不同长度编码字符组成的链（类似于UTF模型，其中特殊字节表示后面的2或3个字节属于单个字符）。这种结构没有简单的基址偏移索引，必须总是从开头迭代才能到达第N个元素。

请注意，我使用unicodeScalars而不是Character，因为它们是16位固定长度表示字符的方式，允许直接进行二进制比较。Character类型并不那么直截了当，比较时间更长。

- Alain T.

Answer 2

试试这个：

extension String {
    func hammingDistance(to other: String) -> Int? {
        guard self.characters.count == other.characters.count else { return nil }

        return zip(self.characters, other.characters).reduce(0) { distance, chars in
            distance + (chars.0 == chars.1 ? 0 : 1)
        }
    }
}

print("read".hammingDistance(to: "hear")) // => 2

- Alexander

---

a.characters和b.characters可以保存在本地变量中。 - user28434'mstep

@user28434 为了什么目的？ - Alexander

characters 属性的 getter 可能会有计算开销。 - user28434'mstep

很遗憾，你的算法在我的问题上花了161秒才完成。不过看起来相当漂亮和简洁。 - Logan Jahnke

你有哪两个字符串？ - Bence Pattogato

Answer 3

以下代码在0.07秒内执行了8500个字符：

func getHammingDistance(w1: String, w2: String) -> Int {
    if w1.characters.count != w2.characters.count {
        return -1
    }

    let arr1 = Array(w1.characters)
    let arr2 = Array(w2.characters)

    var counter = 0
    for i in 0 ..< arr1.count {
        if arr1[i] != arr2[i] { counter += 1 }
    }

    return counter
}

- Bence Pattogato

---

通过 w1 和 w2 的 1 次迭代比较计数，通过 w1 的 1 次迭代将其内容不必要地复制到数组中，然后对于 w2 做同样的操作，最后进行一次迭代以比较字符。这是 5 次迭代，而我的解决方案只需要 3 次。 - Alexander

仍然更快 :) - Bence Pattogato

它比我的算法更高效，但仍然远不及它的Java对应版本快。结果为134秒。 - Logan Jahnke

使用什么输入数据？编译器优化已启用吗？ - Alexander

Answer 4

经过一些尝试，我找到了比@Alexander的答案（以及我之前错误的回答）更快的解决方案。

extension String {
    func hammingDistance(to other: String) -> Int? {
        guard !self.isEmpty, !other.isEmpty, self.characters.count == other.characters.count else {
            return nil
        }

        var w1Iterator = self.characters.makeIterator()
        var w2Iterator = other.characters.makeIterator()

        var distance = 0;
        while let w1Char = w1Iterator.next(), let w2Char = w2Iterator.next()  {
            distance += (w1Char != w2Char) ? 1 : 0
        }
        return distance
    }
}

在我的电脑上，对于比较包含一百万个字符的字符串，时间分别为1.078秒和1.220秒，因此大约提高了10%。我猜测这是由于避免使用 .zip 和稍微减少了 .reduce 和元组的开销所致。

- GetSwifty

Answer 5

*已失效*，请查看新答案

我的方法：

private func getHammingDistance(w1: String, w2: String) -> Int {
    guard w1.characters.count == w2.characters.count else {
        return -1
    }
    let countArray: Int = w1.characters.indices
        .reduce(0, {$0 + (w1[$1] == w2[$1] ? 0 : 1)})
    return countArray
}

比较两个包含10,000个随机字符的字符串只需要0.31秒。

稍作扩展：这只需要一次迭代，同时不断添加即可。

此外，它更加简洁。

- GetSwifty

---

你的代码无法编译。即使修复了，从testText.characters.indices中获取的索引仅对testText有效。你的代码（如果修复）只在一些非常受限制的条件下工作。 - OOPer

你尝试过像这样的代码吗？print(getHammingDistance(w1: "", w2: "abc")) - OOPer

我已经修复了变量名称并正在解决问题。同时期待Swift 4的到来。 - GetSwifty

@OOPer 请看新答案。找到了更好更快的解决方案。 - GetSwifty

Answer 6

正如其他人所指出的那样，反复调用 .characters 需要时间。如果您将所有字符串都转换一次，应该会有所帮助。

func connectData() {
    let verticies = graph.canvas // canvas is Array<Node>
                                 // Node has key that holds the String
    // Convert all of the keys to utf16, and keep them
    let nodesAsUTF = verticies.map { $0.key!.utf16 }

    for vertex in 0 ..< verticies.count {
        for compare in vertex + 1 ..< verticies.count {
            if getHammingDistance(w1: nodesAsUTF[vertex], w2: nodesAsUTF[compare]) == 1 {
                graph.addEdge(source: verticies[vertex], neighbor: verticies[compare])
            }
        }
    }
}

// Calculate the hamming distance of two UTF16 views
func getHammingDistance(w1: String.UTF16View, w2: String.UTF16View) -> Int {
    if w1.count != w2.count {
        return -1
    }

    var counter = 0
    for i in w1.startIndex ..< w1.endIndex {
        if w1[i] != w1[i] {
            counter += 1
        }
    }
    return counter
}

我使用了UTF16，但根据数据，您可能想尝试UTF8。由于我没有您正在使用的字典，请告诉我结果！

- rjpadula