优化将破折号添加到长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秒.

Answer 2

正如哈米什的回答中已经指出的，你应该避免这两件事：

• 计算每个指数string.index(string.startIndex, offsetBy: ...)
• 修改一个大字符串insert(_:at:)

所以，这可以是另一种方式：

func reformatDebugString4(string: String) -> String {
    var result = ""

    var currentIndex = string.startIndex
    while currentIndex < string.endIndex {
        let nextIndex = string.index(currentIndex, offsetBy: 2, limitedBy: string.endIndex) ?? string.endIndex
        if currentIndex != string.startIndex {
            result += "-"
        }
        result += string[currentIndex..<nextIndex]
        currentIndex = nextIndex
    }

    return result
}