はじめに
先日、iOSDC2017で「最近話題のあのサービスの番組表の実装を紐解く」という内容で登壇させていただきました。CfPを出して選出され登壇するという流れは初めてで、とても貴重な体験となりました。ありがとうございました。
そんな中、登壇者への質問に対してこんな内容のものがありました。
「表示されているCellと移動後のCellの比較に、なぜArrayを使っているのですか？」と。
それは、セッションの中で紹介させていただいたライブラリに対してのものだったのですが、私が以前これを実装していく過程で検証した結果として「Setは遅いから」という発言をしました。ただ、質問を受けた時点でSetの何が遅いのかということを説明できなかったことと、Arrayの方が遅いという意見をいただき、これについて後日検証したので書き残します。
検証
前提
Setには、論理演算するための様々なメソッドがあります。Setを使う利点としてはこれらのメソッドを利用できることにあります。
公式ドキュメントから画像だけお借りするとして、詳しくはそちらをご覧ください。
Arrayでこれらのことを行おうとすると、走査のためにループを回しエレメントに対する比較を行う必要があるので、以下のようなメソッドを作成しています。
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
let array = Array(0..<1000)
array.intersection(array)
// 2.86191099882126
Set
let set = Set(0..<1000)
set.intersection(set)
// 0.00128000974655151
結果
圧倒的Setの勝利です。3秒弱も掛かっていたらユーザー体験を大きく損ないます。当然ですが、件数が増えれば増えるほどこの差は恐ろしく広がっていきます。ただ、実際の表示状態であれば1000件もの比較は行われることはまず無さそうなので、そこまで体感は変わらないのでしょう。通常表示されているUIViewの数は、せいぜい数十件程度です。
2. 差集合
次に、表示範囲から消えてしまったCellや新たに表示する必要があるCellを探し出してみます。これには、集合aと集合bのどちらか一方にしかないデータを抽出する必要があります。
今回はsubtractingというメソッドを利用します。
Array
let array = Array(0..<1000)
array.subtracting(array)
// 0.0378379821777344
Set
let set = Set(0..<1000)
set.subtracting(set)
// 0.000542998313903809
結果
こちらもintersection同様にSetの圧勝です。Setの方が遅いと啖呵切ったことをそろそろ後悔してきてます。これら論理演算を行うなら、言われたとおりSetの方が速いです。ぐうの音も出ません。
3. 追加
ただ、Arrayの方が速い処理はあります。Setは一意性を担保するため地道にinsertなどをやっていくと、その度に比較が行われるためどうしてもその処理が遅くなってしまいます。Arrayはそのまま追加するだけなのでだいぶ速いです。
Array
var a: Array<Int> = []
(0..<1000).forEach {
a.append($0)
}
// 0.0481240153312683
Set
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での比較ではないためどれか一つしか残らないので注意が必要です。
let array = Array(0..<1000)
Set(array)
// 0.00909197330474854
もちろんHashableに準拠しているものにしか使えませんが、1000件のデータで約0.009秒です。上記を利用してextensionのメソッドを書き直してみます。
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を実行してもそこまでパフォーマンスが落ちることはないと思います。
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
let array = Array(0..<1000)
array.intersection(array)
// 0.00995397567749023
subtracting
array.subtracting(array)
// 0.00112402439117432
最初の状態よりintersectionで約270倍、subtractingで約33倍ほど改善されました。これでもSetよりはまだ2~10倍ほど遅いのですが、Setのinsertはそこそこコストが掛かるので、トータルで見るとまた結果が違ってきます。
Array
var array: Array<Int> = []
(0..<1000).forEach {
array.append($0)
}
array.intersection(array)
array.subtracting(array)
// 0.0469570159912109
Set
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で論理演算を高速に行う方法募集中 