[Swift] String部分参照の処理性能に注意

まずは、以下のコードと処理時間を見てもらいたい

10万文字の文字列を1文字づつアクセスすると、

コード1

let string = String(repeating: "0123456789", count: 10000)
let length = string.count
print("length: \(length)")

extension String {
    subscript(at: Int) -> Character { self[self.index(self.startIndex, offsetBy: at)] }
}

let t1 = measureTimeSeconds {
    for n in 0 ..< length {
        let ch = string[n]
        // nop
    }
}
print("subscript:", t1 * 1000, "ms")

な なんと47秒超え。あまりの遅さに絶句。これに気付かず何度もTLE(Time Limit Exceeded)を喰らった.
extensionやめて直接書いてもほとんど変わらない。

結果1

length: 100000
subscript: 47260.40498 ms

下記の通り`measureTimeSeconds`はblockの処理時間を秒で返す関数。

共通コード

func measureTimeSeconds(block: (() -> Void)) -> Double {
    let startTime = Date()
    block()
    let duration = -startTime.timeIntervalSinceNow
    return duration
}

measureTimeSeconds自身のオーバーヘッドは約30ナノ秒と無視できる性能。

100万回の平均値

var total = 0.0
for _ in 0 ..< 1000000 {
    let t = measureTimeSeconds {
        // nop
    }
    total += t
}
print("measureTimeSeconds:", total * 1000 * 1000 * 1000 / 1000000, "ns")
//-> measureTimeSeconds: 30.085206031799316 ns

では、一旦、配列に変換したらどの程度か？

コード2

let t2 = measureTimeSeconds {
    //let array = string.map { $0 }
    let array = Array(string)
    for n in 0 ..< length {
        let ch = array[n]
        // nop
    }
}
print("array:", t2 * 1000, "ms")

配列への変換を含めて、たったの3.8ミリ秒。この差（上との差）は何だ！

結果2

array: 3.83301576 ms

for-inはどの程度か？

これまでの例のように、文字列を先頭から末尾に向かって（もしくは、末尾から先頭に向かって）順に走査するだけなら、for-in(for-in loop to iterate over a sequence)でよい。この場合の性能はどうか？

コード3

let t3 = measureTimeSeconds {
    for ch in string {
        // nop
    }
}
print("for-in:", t3 * 1000, "ms")

let t4 = measureTimeSeconds {
    for ch in string.reversed() {
        // nop
    }
}
print("for-in (reversed):", t4 * 1000, "ms")

1.7ミリ秒、さすがに速い。
リバースでも2.1ミリ秒と高速。

結果3

for-in: 1.657684644 ms
for-in (reversed): 2.124031385 ms

今回の教訓

• StringをCやC++の様に文字の配列としてアクセスすると、とんでもなく時間を要す
• Stringを先頭から末尾に向かって（もしくは、末尾から先頭に向かって）順に走査するだけならfor-in(for-in loop to iterate over a sequence)を使う
• 何度もアクセスしたり、一様なアクセスでは無い場合は、Arrayに変換してからアクセスする
• 部分文字列(Substring)も同様に遅いと考えられる

計測条件

• PC ： MacBook Pro 2019（Intel Core i5 2.4GHz）
• OS ： macOS 12.1 (21C52)
• Swift ： Version 5.5.2 (swiftlang-1300.0.47.5 clang-1300.0.29.30)
• コンパイル ： swiftc -Ounchecked test.swift -o a.out
• 実行 ： ./a.out
• 3回実行した平均値

追記（遅い理由を探ってみた）

String[String.index(String.startIndex, offsetBy: at)]は、もしかして、offsetByの位置まで毎回先頭から走査しているのでは？

アクセス位置を10倍づつずらしてアクセスを繰り返してみると、

let string = String(repeating: "0123456789", count: 10001)
let length = string.count
print("length: \(length)")

extension String {
    subscript(at: Int) -> Character { self[self.index(self.startIndex, offsetBy: at)] }
}

for at in [1, 10, 100, 1000, 10000, 100000] {
    let t = measureTimeSeconds {
        for n in 0 ..< 10000 {
            let ch = string[at]
            // nop
        }
    }
    print("at:", at, t * 1000, "ms / 10000")    
}

予想通り、ほぼ1桁づつ処理時間が伸びていく。

結果

length: 100010
at:      1    0.30791759490966797 ms / 10000
at:     10    1.425027847290039 ms / 10000
at:    100   11.00003719329834 ms / 10000
at:   1000  101.6700267791748 ms / 10000
at:  10000 1001.6210079193115 ms / 10000
at: 100000 9921.151041984558 ms / 10000

内部はUnicodeでマルチバイト文字のため、アクセス位置を直接計算では求められないと想定した。まあ確かにそうだ。
競プロではArrayに変換してから使うのが正解だな。