Setは遅いのか

## はじめに

先日、iOSDC2017で「[最近話題のあのサービスの番組表の実装を紐解く](https://speakerdeck.com/kyoheig3/iosdc-2017)」という内容で登壇させていただきました。CfPを出して選出され登壇するという流れは初めてで、とても貴重な体験となりました。ありがとうございました。

そんな中、登壇者への質問に対してこんな内容のものがありました。

「表示されている`Cell`と移動後の`Cell`の比較に、なぜ`Array`を使っているのですか？」と。

それは、[セッションの中で紹介させていただいたライブラリ](https://github.com/KyoheiG3/GridView)に対してのものだったのですが、私が以前これを実装していく過程で検証した結果として「`Set`は遅いから」という発言をしました。ただ、質問を受けた時点で`Set`の何が遅いのかということを説明できなかったことと、`Array`の方が遅いという意見をいただき、これについて後日検証したので書き残します。

## 検証

### 前提

`Set`には、論理演算するための様々なメソッドがあります。`Set`を使う利点としてはこれらのメソッドを利用できることにあります。

[公式ドキュメント](https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/CollectionTypes.html#//apple_ref/doc/uid/TP40014097-CH8-ID490)から画像だけお借りするとして、詳しくはそちらをご覧ください。

![setVennDiagram_2x.png](https://qiita-image-store.s3.amazonaws.com/0/36424/aea6054d-3f4b-11fc-be97-3c0f234a6ceb.png)

`Array`でこれらのことを行おうとすると、走査のためにループを回しエレメントに対する比較を行う必要があるので、以下のようなメソッドを作成しています。

```swift
extension Array where Element: Equatable {
    func subtracting(_ elements: [Element]) -> [Element] {
        var copy = self
        for element in elements {
            if let index = copy.index(of: element) {
                copy.remove(at: index)
            }
        }

        return copy
    }

    func intersection(_ elements: [Element]) -> [Element] {
        var copy: [Element] = []
        for element in elements {
            if index(of: element) != nil {
                copy.append(element)
            }
        }

        return copy
    }
}
```
_※後述しますが、もっと効率のいい方法がありそうです。_

### 1. 積集合

`UIScrollView`上に並んでいる`Cell`を、ある状態aと、aからいずれかの方向にスクロールされた状態bの間で、表示状態が重複している`Cell`を探し出します。この実装を行う場合は、集合aと集合bのそれぞれを比較し重複分を抽出します。

`Set`にはもともと`intersection`というメソッドが存在するのでこれを利用します。`Array`にも同様のメソッドを`extension`で追加してあります。

では、1000件の重複データを、`Set`と`Array`で取り出してみます。

#### Array

```swift
let array = Array(0..<1000)
array.intersection(array)
// 2.86191099882126
```

#### Set

```swift
let set = Set(0..<1000)
set.intersection(set)
// 0.00128000974655151
```

#### 結果

圧倒的`Set`の勝利です。3秒弱も掛かっていたらユーザー体験を大きく損ないます。当然ですが、件数が増えれば増えるほどこの差は恐ろしく広がっていきます。ただ、実際の表示状態であれば1000件もの比較は行われることはまず無さそうなので、そこまで体感は変わらないのでしょう。通常表示されている`UIView`の数は、せいぜい数十件程度です。

### 2. 差集合

次に、表示範囲から消えてしまった`Cell`や新たに表示する必要がある`Cell`を探し出してみます。これには、集合aと集合bのどちらか一方にしかないデータを抽出する必要があります。
今回は`subtracting`というメソッドを利用します。

#### Array

```swift
let array = Array(0..<1000)
array.subtracting(array)
// 0.0378379821777344
```

#### Set

```swift
let set = Set(0..<1000)
set.subtracting(set)
// 0.000542998313903809
```

#### 結果

こちらも`intersection`同様に`Set`の圧勝です。`Set`の方が遅いと啖呵切ったことをそろそろ後悔してきてます。これら論理演算を行うなら、言われたとおり`Set`の方が速いです。ぐうの音も出ません。

### 3. 追加

ただ、`Array`の方が速い処理はあります。`Set`は一意性を担保するため地道に`insert`などをやっていくと、その度に比較が行われるためどうしてもその処理が遅くなってしまいます。`Array`はそのまま追加するだけなのでだいぶ速いです。

#### Array

```swift
var a: Array<Int> = []
(0..<1000).forEach {
    a.append($0)
}
// 0.0481240153312683
```

#### Set

```swift
var s: Set<Int> = []
(0..<1000).forEach {
    s.insert($0)
    return // return しないと2倍ループしてしまう
}
// 0.140631020069122
```

#### 結果

割合としては`Set`の方が3倍程度ですが、時間的には思ったよりも掛かっている気がします。`Set`を使いつつもパフォーマンス改善したければ`insert`を減らす必要がありそうです。

## 改善

上記を踏まえると、論理演算は`Set`を使い、集合の生成には`Array`を使うというイイトコドリの実装ができれば幸せになれそうです。

ということで、`extension`で追加した`Array`のメソッドたちを見直してみましょう。
おわかりだと思いますが、内部で`for`を回している時点で終わっています。ここを改善していきたいのですが、手っ取り早く行うには`Set`を使います。検証していると、`Set`の`insert`は遅いのですが、イニシャライザに`Array`を渡して初期化する分にはそのコストがほとんどかからないことが分かりました。

ただ、`Array`のリストに重複したデータが複数ある場合は`hashValue`での比較ではないためどれか一つしか残らないので注意が必要です。

```swift
let array = Array(0..<1000)
Set(array)
// 0.00909197330474854
```

もちろん`Hashable`に準拠しているものにしか使えませんが、1000件のデータで約`0.009`秒です。上記を利用して`extension`のメソッドを書き直してみます。

```swift
extension Array where Element: Equatable, Element: Hashable {
    func subtracting(_ elements: [Element]) -> [Element] {
        return Array(Set(self).subtracting(elements))
    }

    func intersection(_ elements: [Element]) -> [Element] {
        return Array(Set(self).intersection(elements))
    }
}
```

オーダーが気になるようであれば、`Comparable`に準拠して`sorted`を実行してもそこまでパフォーマンスが落ちることはないと思います。

```swift
extension Array where Element: Equatable, Element: Hashable, Element: Comparable {
    func subtracting(_ elements: [Element]) -> [Element] {
        return Array(Set(self).subtracting(elements)).sorted()
    }

    func intersection(_ elements: [Element]) -> [Element] {
        return Array(Set(self).intersection(elements)).sorted()
    }
}
```

### 再検証

上記のように変更して再度検証してみます。

#### intersection

```swift
let array = Array(0..<1000)
array.intersection(array)
// 0.00995397567749023
```

#### subtracting

```swift
array.subtracting(array)
// 0.00112402439117432
```

最初の状態より`intersection`で約270倍、`subtracting`で約33倍ほど改善されました。これでも`Set`よりはまだ2~10倍ほど遅いのですが、`Set`の`insert`はそこそこコストが掛かるので、トータルで見るとまた結果が違ってきます。

#### Array

```swift
var array: Array<Int> = []
(0..<1000).forEach {
    array.append($0)
}
array.intersection(array)
array.subtracting(array)
// 0.0469570159912109
```

#### Set

```swift
var set: Set<Int> = []
(0..<1000).forEach {
    set.insert($0)
    return // return しないと2倍ループしてしまう
}
set.intersection(set)
set.subtracting(set)
// 0.136337995529175
```

改善後に一連の処理を行うと、`Array`の方が速いことが分かりました。

## まとめ

今回ことの発端となった「`Set`は遅いから」発言に関して言うと私の論点が違ったという恥ずかしい内容ですが、実装全体で見ていくと`Set`の方が遅いこともあるというふうに捉えていただければ幸いです。

また、今回の検証中に改善してみた方法は`Array`本来の目的を逸脱する破壊的処理を含むことと`Array`に追加された要素を一意にしておく必要があるため、`Set`の遅い処理を減らすといったアプローチの方が見通しは良いと感じました。論理演算が目的で、それを多用するのであれば`Set`を利用し、リストとして値を列挙したりしたいのであれば`Array`を使うようにしましょう。（初期化だけ`Array`にするとかはなくはないかも）

_Arrayで論理演算を高速に行う方法募集中 :fearful:_