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

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

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

```swift:コード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*やめて直接書いてもほとんど変わらない。

```swift:結果1
length: 100000
subscript: 47260.40498 ms
```

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

```swift:共通コード
func measureTimeSeconds(block: (() -> Void)) -> Double {
    let startTime = Date()
    block()
    let duration = -startTime.timeIntervalSinceNow
    return duration
}
```

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

```swift: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
```


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

```swift:コード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ミリ秒。この差（上との差）は何だ！

```swift:結果2
array: 3.83301576 ms
```


# `for-in`はどの程度か？

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

```swift:コード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ミリ秒と高速。

```swift:結果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倍づつずらしてアクセスを繰り返してみると、

```swift:
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桁づつ処理時間が伸びていく。

```swift:結果
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*に変換してから使うのが正解だな。