时间戳

首页 > 解决方案 > Swift String 的 count 属性时间复杂度

swift - Swift String 的 count 属性时间复杂度

问题描述

我想知道 Swift (Swift 5) String 的 count 属性的时间复杂度是多少？我发现它很慢。

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

与 Array 的 count 属性相比，我对其进行了一些测试，后者的速度更快。

在我的机器上测试结果：

测试用例“-[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
            }
        }
    }

}

标签： swiftswift5

解决方案

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

某些集合操作的性能取决于集合提供的索引类型。例如，可以在 O(1) 时间内测量两个索引之间的距离的随机访问集合，可以在 O(1) 时间内计算其计数属性。相反，因为前向或双向集合必须遍历整个集合来计算包含元素的数量，所以访问它的 count 属性是一个 O(n) 操作。

因此，您可以预期String.count比Array.count.

推荐阅读