Optimizing adding dashes to a long Swift String

Question

I am trying to take a hex string and insert dashes between every other character (e.g. "b201a968" to "b2-01-a9-68"). I have found several ways to do it, but the problem is my string is fairly large (8066 characters) and the fastest I can get it to work it still takes several seconds. These are the ways I have tried and how long they are taking. Can anyone help me optimize this function?

//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

The problem with all three of your approaches is the use of index(_:offsetBy:) in order to get the index of the current character in your loop. This is an O(n) operation where n is the distance to offset by – therefore making all three of your functions run in quadratic time.

Furthermore, for solutions #1 and #3, your insertion into the resultant string is an O(n) operation, as all the characters after the insertion point have to be shifted up to accommodate the added character. It's generally cheaper to build up the string from scratch in this case, as we can just add a given character onto the end of the string, which is O(1) if the string has enough capacity, O(n) otherwise.

Also for solution #1, saying myString.characters.count is an O(n) operation, so not something you want to be doing at each iteration of the loop.

So, we want to build the string from scratch, and avoid indexing and calculating the character count inside the loop. Here's one way of doing that:

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

Your best solution (#3) in a release build took 37.79s on my computer, the method above took 0.023s.

Answer 2

As already noted in Hamish's answer, you should avoid these two things:

• calculate each index with string.index(string.startIndex, offsetBy: ...)
• modifying a large String with insert(_:at:)

So, this can be another way:

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
}