swift - 优化向长 Swift 字符串添加破折号

Question

我正在尝试获取一个十六进制字符串并在每个其他字符之间插入破折号(例如“b201a968”到“b2-01-a9-68”)。我已经找到了几种方法来做到这一点，但问题是我的字符串相当大(8066 个字符)并且我可以让它工作的最快速度仍然需要几秒钟。这些是我尝试过的方法以及它们需要多长时间。谁能帮我优化这个功能？

//42.68 seconds
    func reformatDebugString(string: String) -> String
    {
        var myString = string
        var index = 2
        while(true){
            myString.insert("-", at: myString.index(myString.startIndex, offsetBy: index))
            index += 3
            if(index >= myString.characters.count){
                break
            }
        }

        return myString
    }

---

//21.65 seconds
    func reformatDebugString3(string: String) -> String
    {
        var myString = ""
        let length = string.characters.count
        var first = true
        for i in 0...length-1{
            let index = string.index(myString.startIndex, offsetBy: i)
            let c = string[index]

            myString += "\(c)"
            if(!first){
                myString += "-"
            }
            first = !first
        }

        return myString
    }

---

//11.37 seconds
    func reformatDebugString(string: String) -> String
    {
        var myString = string
        var index = myString.characters.count - 2
        while(true){
            myString.insert("-", at: myString.index(myString.startIndex, offsetBy: index))
            index -= 2
            if(index == 0){
                break
            }
        }

        return myString
    }

Answer 1

这三种方法的问题在于使用 index(_:offsetBy:) 来获取循环中当前字符的索引。这是一个复杂度为 O(n) 的操作，其中 n 是要抵消的距离——因此使所有三个函数都以二次方时间运行。

此外，对于解决方案 #1 和 #3，插入结果字符串是一个 O(n) 操作，因为插入点之后的所有字符都必须向上移动以容纳添加的字符。在这种情况下，从头开始构建字符串通常更便宜，因为我们只需将给定字符添加到字符串的末尾，如果字符串有足够的容量，则为 O(1)，否则为 O(n)。

同样对于解决方案 #1，说 myString.characters.count 是一个 O(n) 操作，因此您不想在循环的每次迭代中都执行此操作。

因此，我们希望从头开始构建字符串，并避免在循环内索引和计算字符数。这是一种方法:

extension String {

    func addingDashes() -> String {

        var result = ""

        for (offset, character) in characters.enumerated() {

            // don't insert a '-' before the first character,
            // otherwise insert one before every other character.
            if offset != 0 && offset % 2 == 0 {
                result.append("-")
            }

            result.append(character)
        }
        return result
    }
}

// ...

print("b201a968".addingDashes()) // b2-01-a9-68

发布版本中的最佳解决方案(#3)在我的计算机上花费了 37.79 秒，上面的方法花费了 0.023 秒。