Swift 字符串的计数属性时间复杂度

Question

我想知道 Swift (Swift 5) 字符串的计数属性的时间复杂度是多少？我发现它很慢。

我猜它是 O(n)，线性时间复杂度，但找不到任何关于它的文档。有人可以帮忙吗？

我做了个小测试，对比Array的计数属性快多了。

我机器上的测试结果：

测试用例“-[TESTS.TESTS testArrayCountPerformance]”通过（1.686 秒）。

测试用例“-[TESTS.TESTS testStringCountPerformance]”通过（11.113 秒）。

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

}

Answer 1

Array符合RandomAccessCollection。 String 符合 BidirectionalCollection。如果您查看 Collection 协议的 documentation，您会发现：

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.

因此，您可以预期 String.count 比 Array.count 的计算成本更高。

Swift 字符串的计数属性时间复杂度

Swift String's count property time complexity

swift

swift5

Swift 字符串的计数 属性 时间复杂度

Swift String's count property time complexity

swift

swift5

Swift 字符串的计数属性时间复杂度