Swift String's count property time complexity

Question

I'm wondering about what the time complexity of Swift (Swift 5) String's count property is? I found it is very slow.

I guess it's O(n), linear time complexity, but cannot find any document about it. Can any one help?

I made a little test about it, compared with Array's count property which is way more faster.

Test result on my machine:

Test Case '-[TESTS.TESTS testArrayCountPerformance]' passed (1.686 seconds).

Test Case '-[TESTS.TESTS testStringCountPerformance]' passed (11.113 seconds).

class TESTS: XCTestCase {

    let letters = Array("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789")

    var randomString = ""
    var randomChars: [Character] = []

    override func setUp() {
        for _ in 0..<1000000 {
            randomString += String(letters[Int.random(in: 0..<letters.count)])
        }
        randomChars = Array(randomString)
    }

    func testStringCountPerformance() {
        measure {
            for _ in 0..<100 {
                _ = randomString.count
            }
        }
    }

    func testArrayCountPerformance() {
        measure {
            for _ in 0..<100 {
                _ = randomChars.count
            }
        }
    }

}

score 4 · Accepted Answer · answered Apr 30 '20 at 06:21

Array conforms to RandomAccessCollection. String conforms to BidirectionalCollection. If you look at the documentation for the Collection protocol you'll find this:

The performance of some collection operations depends on the type of index that the collection provides. For example, a random-access collection, which can measure the distance between two indices in O(1) time, can calculate its count property in O(1) time. Conversely, because a forward or bidirectional collection must traverse the entire collection to count the number of contained elements, accessing its count property is an O(n) operation.

So, you can expect String.count to be more computationally expensive than Array.count.

Swift String's count property time complexity

1 Answers1