[Swift] Swiftでポインタを使って処理を高速化してみる

# 前書き

Swiftのような**高級言語([高水準言語](https://www.weblio.jp/content/%E9%AB%98%E6%B0%B4%E6%BA%96%E8%A8%80%E8%AA%9E))**を書いている人にとって、普段は**ポインタを意識すること**はないでしょう。

今回はそんな世界へと一歩踏み入れてみましょう！


# ポインタを使った高速化

簡単な例を使って見ていきましょう。

## Example1

### 1. コード例

0~1000の数字を合計するだけの処理を考えた時、以下のようになります。

```.swift
func runLoopNumbers() {    
    var sum = 0

    for i in (0...1000) {
        sum += i
    }
}
```

これをポインタを用いた場合は、以下のように書けます。

```.swift
func runLoopPointerNumbers() {            
    var sum = 0
    let sumPointer = UnsafeMutablePointer<Int>(&sum)
    
    for i in (0...1000) {
        sumPointer.pointee += i
    }
}
```

この``UnsafeMutablePointer``というのを用いることでポインタを表しています。
（表すための方法がいくつかあり、[参考文献](#参考文献)の方に詳しく載せているのでそちらをご覧ください）


### 2. 比較結果

それぞれ**１０回**ずつ実行した結果とその平均時間を取ると

|回数|ポインタなし|ポインタあり|
| ---- | ---- | ---- |
|1回目| 2.10E-02 | 7.37E-04 |
|2回目| 9.09E-03 | 7.12E-04 |
|3回目| 9.41E-03 | 7.10E-04 |
|4回目| 9.87E-03 | 7.16E-04 |
|5回目| 9.72E-03 | 7.19E-04 |
|6回目| 9.12E-03 | 7.25E-04 |
|7回目| 1.01E-02 | 7.26E-04 |
|8回目| 9.05E-03 | 7.28E-04 |
|9回目| 9.14E-03 | 7.30E-04 |
|10回目| 8.93E-03 | 7.15E-04 |
|Average| 1.05E-02 | 7.22E-04 |
|| = **0.010539**| = **0.000722** |

実行時間が１秒にも満たないので、一見たいしたことはないかもしれませんが...
**実行速度に15倍程の差**がついていることがわかります。

※ DateのtimeIntervalSinceで計測
※ E-01 = 10^-1 = 1/10

## Example2

海外の競技プログラミングでお馴染みLeetCodeの[「1. Two Sum」](https://leetcode.com/problems/two-sum/)という問題を例にとってみましょう。

### 0. 前提

問題は以下のようになっています。

```
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
```

つまり
「**与えられた配列（nums）から２つを選択し、指定した値(target)を作れるかどうか**」
ということになります。

その最初の例として、以下が与えられます。

```
Given nums = [2, 7, 1, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
```


### 1. コード例

愚直に``for``や``while``を使って解けば、このようになるでしょう。（あくまで一例として）

```.swift
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    for i in 0 ..< nums.count {
        var j = i+1
        
        while j < nums.count {
            if nums[i] + nums[j] == target {
                return [i, j]
            }
            j += 1
        }
    }
    return []
}
```
シンプルに配列を２回調査する線形探索をしています。

これをポインタを用いた場合は、以下のように書けます。

```.swift
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var newNums = nums
    let pointer = UnsafeMutablePointer<Int>(&newNums)
    
    for i in 0 ..< nums.count {
        var j = i+1
        
        while j < nums.count {
            if pointer[i] + pointer[j] == target {
                return [i, j]
            }
            j += 1
        }
    }
    return []
}
```

``var newNums = nums``としているのが冗長ですが、ポインタを使うために仕方なく置く必要があります。


### 2. 比較結果

|ポインタなし|ポインタあり|
| ---- | ---- |
| 24ms | 8ms |

実行速度が**3倍早く**なっていることがわかります。
処理が重たいものであればもっと顕著な差が出せるでしょう。

### 3. 余談

ちなみにポインタを使わなくても、この問題は高速にできるので載せておきます。（あくまで一例として）

```.swift
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var keyValue = [Int: Int]()
    
    for (i, num) in nums.enumerated() {
        if let index = keyValue[target-num] {
            return [i, index]
        }
        keyValue[num] = i
    }
    return []
}
```

数字をkeyとして値をキャッシュしておき検索する（ハッシュテーブルを使う）方法です。
これであれば、**O(n)**で済むのでかなり高速です。

実行時間は**8ms**で**ポインタを使った時と同じ速度**を出すことができました。

## 終わりに

実務で使うというのはなかなか難しいかもしれません。
競技プログラミングのような**ロジックだけを考える**、といった部分的な使い方であればとても入りやすいでしょう。


ただ、余談でも紹介しましたが...
ポインタを使う前に**アルゴリズムをちゃんと用いる**ことで高速化できることが多いです。


とはいえ、触ってみてるのは楽しいので、是非みなさんも使ってみてください！

## 参考文献
### Swiftのポインタ関連

- [素晴らしいSwiftのポインタ型の解説](https://qiita.com/omochimetaru/items/c95e0d36ae7f1b1a9052)
- [SwiftでUnsafePointer<T>などのポインタを扱う](https://qiita.com/kaneshin/items/ebabd4f44010568d550f)
- [Swift3のポインタの基礎知識](https://mike-neko.github.io/blog/swift-pointer/)
- [Swiftで書かれたプログラムを1000倍速くした話](https://qiita.com/koher/items/7be570bb0a8ceb4d72be)

### ポインタ関連
- [C 言語にポインタがある理由は省メモリ化・高速化・開発作業の省力化です](http://pg-kura.hatenablog.com/entry/20120616/1339856279)