Что такое BigO of Swift's String.count? - PullRequest
Новая
       49

Что такое BigO of Swift's String.count?

0 голосов
/ 28 мая 2018

Когда swift использует String.count, это:

O (n) , где каждый раз, когда мы его вызываем, мы перебираем всю строку, чтобы посчитать ее

или

O (1) , где swift ранее сохранил размер этого массива и просто обращается к нему.

Ответы [ 3 ]

0 голосов
/ 28 мая 2018

Похоже, O (n) для меня на основе быстрого теста Playground. 

for step in 1...10 {
    let length = step * 100000
    let string = String(repeating: "x", count: length)
    let start = Date()
    let stringLength = string.count
    let end = Date()
    print("Length: \(stringLength), time: \(end.timeIntervalSince(start))")
}

// Length: 100000, time: 0.00178205966949463
// Length: 200000, time: 0.00132298469543457
// Length: 300000, time: 0.00184988975524902
// Length: 400000, time: 0.00218689441680908
// Length: 500000, time: 0.00302803516387939
// Length: 600000, time: 0.00368499755859375
// Length: 700000, time: 0.0039069652557373
// Length: 800000, time: 0.00444602966308594
// Length: 900000, time: 0.0052180290222168
// Length: 1000000, time: 0.00539696216583252
0 голосов
/ 28 мая 2018

Это определенно O(n).Из Swift Book :

В результате число символов в строке не может быть вычислено без итерации по строке для определения границ кластера расширенных графем.Если вы работаете с особенно длинными строковыми значениями, имейте в виду, что свойство count должно перебирать скаляры Юникода во всей строке, чтобы определить символы для этой строки.

Это имеетНесколько последствий, наибольшее из которых - целочисленная подписка (т. е. str[5]), недоступны через стандартную библиотеку.Внутренне String использует кодировку ASCII или UTF-16 (из Swift 5 он использует только UTF-8 ).Если в строке используются только символы ASCII, то count может быть O(1), но ASCII имеет только 127 символов, поэтому рассматривайте это как исключение, а не правило.

NSString, с другой стороны, всегда использует UTF-16, поэтому доступ к его length равен O(1).Также имейте в виду, что NSString.length != String.count (попробуйте строки с эмодзи, и вы увидите).

Что касается вашего второго вопроса, он не кэширует count для последующих вызовов.Таким образом, каждый вызов count равен O(n), даже если строка не изменилась.Код в Foundation РЕПО также подтверждает это.

0 голосов
/ 28 мая 2018

После того, как я не смог найти документацию по этому вопросу или не смог найти эту функцию в исходном коде, я сам проверил это с помощью тестов производительности, как описано ниже.Предполагалось, что O (1) было возможно на основе массива PHP , являющегося O (1).Swifts String.count функция выглядит как O (n) .

Результаты

Unit Test Results

Кэшируется ли count, когда он вызывался раньше?(нет)

Я также проверил, может ли вызов String.count один раз кешировать его.Сравнивая результаты, когда count уже был вызван и когда он был сохранен в переменной, чтобы убедиться, что он не сохраняется до вызова .count в наших обычных тестах.

Caching Tests

Тесты 

import XCTest

class CountTests: XCTestCase {

    func test100K() {
        let testString = String(repeating: "a", count: 100000)
        self.measure {
            _ = testString.count
        }
    }

    func test1000K() {
        let testString = String(repeating: "a", count: 1000000)
        self.measure {
            _ = testString.count
        }
    }

    func test10000K() {
        let testString = String(repeating: "a", count: 10000000)
        self.measure {
            _ = testString.count
        }
    }

    func test10000KCached() {
        let testString = String(repeating: "a", count: 10000000)
        _ = testString.count
        self.measure {
            _ = testString.count
        }
    }

    func test10000KStrong() {
        let testString = String(repeating: "a", count: 10000000)
        let count = testString.count
        self.measure {
            _ = count
        }
    }
}
...