Slow Swift String Performance

Question

I am trying to solve the Palindrome Partitioning Question. You can find the question in https://leetcode.com/problems/palindrome-partitioning/.

And I came up with the solution:

func partition(_ s: String) -> [[String]] {

    var result: [[String]] = []

    func dfs(string: String, partiton: [String]) {

        if string.characters.count == 0 {
            result.append(partiton)
            return
        }

        for length in 1...string.characters.count {

            let endIndex =  string.index(string.startIndex, offsetBy: length-1)
            let part = string[string.startIndex...endIndex]


            if isPalindrome(part) {
                let leftPart = string[string.index(after: endIndex)..<string.endIndex]
                print("string: \(string) part: \(part) leftpart: \(leftPart)")
                dfs(string: leftPart, partiton: partiton + [part])
            }
        }
    }

    func isPalindrome(_ s: String) -> Bool {
        if String(s.characters.reversed()) == s {
            return true
        } else {
            return false
        }
    }

    dfs(string: s, partiton: [])
    return result
}

But the performance is Bad. Time Limit Exceeded.

But the same idea with Python implementation can pass:

def partition(self, s):
    res = []
    self.dfs(s, [], res)
    return res

def dfs(self, s, path, res):
    if not s:
        res.append(path)
        return
    for i in range(1, len(s)+1):
        if self.isPal(s[:i]):
            self.dfs(s[i:], path+[s[:i]], res)

def isPal(self, s):
    return s == s[::-1]

It make me wonder that how to improve the swift implementation and why the swift implementation is slower than python.

Answer 1

A Swift String is a collection of Characters, and a Character represents a single extended grapheme cluster, that can be one or more Unicode scalars. That makes some index operations like "skip the first N characters" slow.

But the first improvement is to "short-circuit" the isPalindrome() function. Instead of building the reversed string completely, compare the character sequence with its reversed sequence and stop as soon as a difference is found:

func isPalindrome(_ s: String) -> Bool {
    return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 }
}

s.characters.reversed() does not create a new collection in reverse order, it just enumerates the characters from back to front. With String(s.characters.reversed()) as in your method however, you force the creation of a new collection for the reversed string, that makes it slow.

For the 110-character string

let string = String(repeating: "Hello world", count: 10)

this reduces the computation time from about 6 sec to 1.2 sec in my test.

Next, avoid index calculations like

let endIndex = string.index(string.startIndex, offsetBy: length-1)

and iterate over the character index itself instead:

func partition(_ s: String) -> [[String]] {

    var result: [[String]] = []

    func dfs(string: String, partiton: [String]) {
        if string.isEmpty {
            result.append(partiton)
            return
        }

        var idx = string.startIndex
        repeat {
            string.characters.formIndex(after: &idx)
            let part = string.substring(to: idx)
            if isPalindrome(part) {
                let leftPart = string.substring(from: idx)
                dfs(string: leftPart, partiton: partiton + [part])
            }
        } while idx != string.endIndex
    }

    func isPalindrome(_ s: String) -> Bool {
        return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 }
    }

    dfs(string: s, partiton: [])
    return result
}

Computation time is now 0.7 sec.

The next step is to avoid string indexing totally, and work with an array of characters, because array indexing is fast. Even better, use array slices which are fast to create and reference the original array elements:

func partition(_ s: String) -> [[String]] {

    var result: [[String]] = []

    func dfs(chars: ArraySlice<Character>, partiton: [String]) {

        if chars.isEmpty {
            result.append(partiton)
            return
        }

        for length in 1...chars.count {
            let part = chars.prefix(length)
            if isPalindrome(part) {
                let leftPart = chars.dropFirst(length)
                dfs(chars: leftPart, partiton: partiton + [String(part)])
            }
        }
    }

    func isPalindrome(_ c: ArraySlice<Character>) -> Bool {
        return !zip(c, c.reversed()).contains { $0 != $1 }
    }

    dfs(chars: ArraySlice(s.characters), partiton: [])
    return result
}

Computation time is now 0.08 sec.

If your string contains only characters in the "basic multilingual plane" (i.e. <= U+FFFF) then you can work with UTF-16 code points instead:

func partition(_ s: String) -> [[String]] {

    var result: [[String]] = []

    func dfs(chars: ArraySlice<UInt16>, partiton: [String]) {

        if chars.isEmpty {
            result.append(partiton)
            return
        }

        for length in 1...chars.count {
            let part = chars.prefix(length)
            if isPalindrome(part) {
                let leftPart = chars.dropFirst(length)
                part.withUnsafeBufferPointer {
                    dfs(chars: leftPart, partiton: partiton + [String(utf16CodeUnits: $0.baseAddress!, count: length)])
                }
            }
        }
    }

    func isPalindrome(_ c: ArraySlice<UInt16>) -> Bool {
        return !zip(c, c.reversed()).contains { $0 != $1 }
    }

    dfs(chars: ArraySlice(s.utf16), partiton: [])
    return result
}

Computation time is now 0.04 sec for the 110 character test string.

---

So some tips which potentially can improve the performance when working with Swift strings are

• Iterate over the characters/indices sequentially. Avoid "jumping" to the n'th position.
• If you need "random" access to all characters, convert the string to an array first.
• Working with the UTF-16 view of a string can be faster than working with the characters view.

Of course it depends on the actual use-case. In this application, we were able to reduce the computation time from 6 sec to 0.04 sec, that is a factor of 150.