Ordered Collection Diffingとは？
Swift5.1で導入される新しい機能です。
Forumスレッド一覧
https://forums.swift.org/search?q=SE-0240
Original Pitch
https://forums.swift.org/t/se-0240-ordered-collection-diffing/19514/34
Proposal
https://github.com/apple/swift-evolution/blob/master/proposals/0240-ordered-collection-diffing.md
Review
https://forums.swift.org/t/se-0240-ordered-collection-diffing/19514/42
https://forums.swift.org/t/amendment-se-0240-ordered-collection-diffing/26084
これはdifference(from:)やdifference(from:by:)を呼び出すことで
2つのコレクションの差分を計算して
何がどう変わっているのかを教えてくれます。
difference(from:)
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/Diffing.swift#L188
またOrdered Collection Diffingは全てSwiftで書かれています。
今回はOrdered Collection Diffingがどういうものなのか
とても参考になる記事がありましたので
そちらを参考に実際の実装などを見ながら
理解をしていきたいと思います。
参考記事
https://www.fivestars.blog/code/swift-5-1-collection-diffing.html
最初に使用される要素を見ていき
その後にメソッドを見ていきたいと思います。
CollectionDifference
GenericなCollectionで
2つの整列されているコレクションの
差分(どの要素が削除され、どの要素が挿入されているのか)を
を保持しています。
A collection of insertions and removals
that describe the difference between two ordered collection states
CollectionDifference
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/CollectionDifference.swift#L16
ChangeElement
比較している要素の型でこれには何の制約も付いていません。
.insertと.removeという2つのケースを持った
CollectionDifference.Changeというenumになっており
個々の要素の変化を表します。(詳細は後ほど記載します)
CollectionDifference.Change
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/CollectionDifference.swift#L19
CollectionDifferenceの特徴
CollectionDifferenceには下記のような特徴があります。
CollectionDifferenceが返す値の順番が決まっている
まず最初に削除された要素のコレクション
その次に追加された要素のコレクションという順番になっています。
これは内部のinitで保証されており
必ず適切な順番になって返ってきます。
CollectionDifferenceの要素はユニークである
initのコメントに下記のような記載があります。
The collection of changes passed as `changes` must meet these
requirements:
- All insertion offsets are unique
- All removal offsets are unique
- All associations between insertions and removals are symmetric
つまり
削除や挿入された要素のオフセットは全てユニークでなければなりません。
また削除と挿入の関係は対称でなければなりません。
また
同じインデックスに対して削除の処理をすることはできません。
挿入に関しても同じです。
さらに
移動した要素は削除と挿入に対になる要素が一つ存在している。
どちらか片方だけというようなものは存在できません。
これは内部でバリデーションをしており
initで不適切なコレクションが渡ってきた場合はnilが返却されます。
_validateChanges
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/CollectionDifference.swift#L89
CollectionDifference.Change
2つのコレクションを比較した時に
変化としては下記の3つのパターンがあります。
- 新しい要素が追加された
- 要素が削除された
- 移動して位置が変わった(元の位置から削除され、新しい位置に挿入された)
そのため
CollectionDifference.Changeは
insertとremoveの2つのenumで表現できます。
CollectionDifference.Change
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/CollectionDifference.swift#L19
それぞれのcaseはoffset element associatedWithという
3つのassociated valuesを持っています。
offset
挿入または削除された位置です。
削除された場合
let oldArray = ["a", "b", "c", "d"]
let newArray = ["a", "b", "d"]
// "c"という要素がindex 2から削除されました
let difference = newArray.difference(from: oldArray)
// differenceは1つの要素を含んだ配列です。
// これは`.remove`で`offset`は2となります。
挿入された場合
let oldArray = ["a", "b", "c", "d"]
let newArray = ["a", "b", "c", "d", "e"]
// "e"という要素がindex 4に挿入されました
let difference = newArray.difference(from: oldArray)
// differenceは1つの要素を含んだ配列です。
// これは`.insert`で`offset`は4となります。
element
実際の要素です。
これがCollectionDifferenceがジェネリックになっている要因です。
let oldArray = ["a", "b", "c", "d"]
let newArray = ["a", "b", "d", "e"]
// "c"という要素をindex 2から削除
// "e"という要素をindex 3に追加
let difference = newArray.difference(from: oldArray)
// differenceは2つの要素の配列
// 最初の要素は.removeでoffset 2、element "c"
// 次の要素は.insertでoffset 3、element "e"
associatedWith
要素を移動した時にこの値が入ります。
insertの場合は移動後のオフセット
removeの場合は移動前のオフセット
が入ります。
これは計算に時間がかかるため
デフォルトでは全てnilとなっており
inferringMoves()を呼び出す必要があります。
inferringMoves
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/CollectionDifference.swift#L323
let oldArray = ["a", "b", "d", "e", "c"]
let newArray = ["a", "b", "c", "d", "e"]
// "c"をindex 4から2へ移動
// - index 4から削除
// - index 2へ追加
let difference = newArray.difference(from: oldArray)
// differenceは2つの要素の配列
// - 最初の要素は`.remove` offset 4 associatedWith nil
// - 次の要素は`.insert` offset 2 associatedWith nil
let differenceWithMoves = difference.inferringMoves()
// differenceWithMovesは2つの要素の配列
// - 最初の要素は`.remove` offset 4 associatedWith 2
// - 次の要素は`.insert` offset 2 associatedWith 4
InferringMoves
CollectionDifferenceインスタンスをスキャンして
削除と挿入のオフセットがマッチした(移動した)要素をコレクションに格納していきます。
もし存在しなければ元のコレクションと同じ要素が含まれたコレクションを返します。
insertionsとremovalsプロパティ
これらの2つのプロパティを使用することで
挿入したChangeと
削除したChangeへ
アクセスすることができます。
insertions
挿入された要素がオフセットが小さいものから順番に並んでいます。
removals
削除された要素がオフセットが小さいものから順番に並んでいます。
CollectionDifferenceの要素の並び順
initの中を見てみるとわかるのですが
要素の順番は
削除が先 挿入があと
になります。
挿入された要素はinsertions配列に入り
削除された要素はremovals配列に入ります。
しかしsubscriptを見てみると
また違った順番で要素を参照しています。
removalsは大きいオフセットから小さいオフセットへ
insertionsは小さいオフセットから大きいオフセットに向かっています。
これは順番に取得した要素を元のコレクション(変化前のコレクション)に適用していくと
新しいコレクションになるようになっており
変化を再現することができます。
let oldArray = ["a", "b", "c", "d"]
let newArray = ["x", "a", "e", "c"]
var anotherArray = oldArray
let difference = newArray.difference(from: oldArray)
// differenceは4つの要素の配列
// 1. `.remove` at offset 3
// 2. `.remove` at offset 1
// 3. `.insert` at offset 0
// 4. `.insert` at offset 2
for change in difference {
switch change {
case let .remove(offset, _, _):
anotherArray.remove(at: offset)
case let .insert(offset, newElement, _):
anotherArray.insert(newElement, at: offset)
}
}
// この時点で`anotherArray`は`newArray`と等しくなる
遷移をたどると下記のようになります。
["a", "b", "c", "d"] // 初期状態
["a", "b", "c"] // "d"をindex 3から削除
["a", "c"] // "b"をindex 1から削除
["x", "a", "c"] // "x"をindex 0へ挿入
["x", "a", "e", "c"] // "e"をindex 2へ挿入
applying
上記ではdifference(from:)で取得した要素をコレクションに順番に適用してきましたが
applying(_:)メソッドを使用することで変化を別のコレクションに適用できます。
let oldArray = ["a", "b", "c", "d"]
let newArray = ["x", "a", "e", "c"]
var anotherArray = oldArray
let difference = newArray.difference(from: oldArray)
// ここでdifferenceをapplyingしている
anotherArray = anotherArray.applying(difference)!
// この時点で`anotherArray`は`newArray`と等しくなる
このメソッドは制約に適合している限りはどんなコレクションにも適用できます。
戻り値としてdifferenceを適用したOptionalなコレクションを返します。
なぜOptionalなのかは
differenceの要素のオフセットが
適用対称のコレクションのオフセットを超えた時に
クラッシュを避けてnilを返すようにしています。
difference(from:)
これまでも出てきましたOrdered Collection Diffingの中心となるメソッドです。
extension BidirectionalCollection where Element : Equatable {
public func difference<C: BidirectionalCollection>(
from other: C
) -> CollectionDifference<Element> where C.Element == Self.Element {
return difference(from: other, by: ==)
}
}
difference(from:)はdifference(from: by:)を呼び出しているだけで
要素がEquatableの時に使用できます。
difference(from: by:)
byに等しくなる条件を指定することでEquatableに適合していない要素にも
differenceを取得することができるようになります。
public func difference<C: BidirectionalCollection>(
from other: C,
by areEquivalent: (Element, C.Element) -> Bool
) -> CollectionDifference<Element>
where C.Element == Self.Element
difference(from:by:)
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/Diffing.swift#L134
シンタックスを見てみると2つのコレクションは
BidirectionalCollectionに適合している必要があります。
つまり前から後からもコレクションの要素へ行ったり来たり参照できることが必要になります。
また2つのコレクションはassociated typeの型は同じである必要があります。
byの条件によってdifferenceで取得できる要素が変わってきます。
例えば全てに対してfalseを返すようにすると
let oldArray = ["a", "b", "c"]
let newArray = ["a", "b", "c"] // 同じ要素
let difference = newArray.difference(from: oldArray,
by: { _, _ in false })
// `difference`は６つの要素を持つ配列:
// - removalsに３要素
// - insertionsに３要素
これは全ての要素の比較がfalseになるので
要素を全部入れ替えたとみなされているからです。
difference(from: by:) の戻り値
Optional ではない CollectionDifferenceを返します。
上記でCollectionDifferenceのinitは
nilを返す可能性があることを紹介しましたが
なぜ違うのか？
これは内部でnilにならないinitを保持しており
そちらを使用しているからです。
これは妥当だと証明されたコレクションを使用しているので
Swift的にもnon-optionalで問題ありません。
difference(from: by:)の内部
まず_CountingIndexCollectionのコレクションを２つ作成し
これを_CollectionChangesへの変換しなおしています。
let source = _CountingIndexCollection(other)
let target = _CountingIndexCollection(self)
let result = _CollectionChanges(from: source, to: target, by: areEquivalent)
_CountingIndexCollectionは実際のコレクションを包んで
開始のindexからのoffsetへアクセスしやすくします。
let originalCollection = ["a", "b", "c", "d"]
let offsetCollection = _CountingIndexCollection(originalCollection)
if let index = offsetCollection.index(of: "d") {
print(index.offset) // 3
print(offsetCollection[index]) // d
}
_CollectionChangesはCollectionDifference.Changeインスタンスの配列です。
その後取得したChangeインスタンスの配列から
CollectionDifferenceのインスタンスを生成して返却しています。
このメソッドないでは実際の差分計算はしておらず
_CollectionChangesの初期化の中で行っています。
_CollectionChanges
２つのコレクションの要素を辿っていき、下記のようなことを行っています。
２つのコレクションの最長共通部分列を取得
https://ja.wikipedia.org/wiki/%E6%9C%80%E9%95%B7%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E5%88%97%E5%95%8F%E9%A1%8C削除と挿入の最短経路を探して最も少ない手順で
sourceコレクションからtargetコレクションへ遷移する方法を見つけます。
https://ja.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E5%95%8F%E9%A1%8C
この２つは表裏一体のような関係となっており
片方が見つかるともう片方も見つかるようになっています。
挿入や削除は非常にコストの高い操作であるため
このプロセスで最も効率差分更新するための方法を導き出すことが
Ordered Collection Diffingの根幹になります。
_CollectionChanges
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/Diffing.swift#L247
ある状態からある状態への遷移方法は複数見つかる中で
もっとも効率の良いものを_CollectionChangesは導き出すことを保証します。
Endpoint
_CollectionChangesの定義の冒頭にあるtypealiasです。
typealias Endpoint = (x: SourceIndex, y: TargetIndex)
これはsourceコレクションとtargetコレクションの関係を表します。
例えばsourceコレクションの最初の要素とtargetコレクションの２番目の要素を関連づけたい場合
Endpointは(1,2)と定義します。
pathStorage
ここからは_CollectionChangesが
具体的にどういう計算をしているのかを見ていきます。
下記のような２次元のチャートがあります。
x軸がsourceのコレクションを
y軸はtargetのコレクションを表します。
| • | X | A | B | C | D |
• | | | | | | |
X | | | | | | |
Y | | | | | | |
C | | | | | | |
D | | | | | | |
左上を(0,0)として一番右下の(lastIndexOfTarget, lastIndexOfSource)を目指します。
下記のようなイメージです。
```
| • | X | A | B | C | D |
• | S | | | | | |
X | | | | | | | // S: 開始
Y | | | | | | | // T: 目的地
C | | | | | | |
D | | | | | | T |
// 開始位置 S: (0,0)
// 目的位置 T: (4,5)
```
ルール
- 左から右にしか移動できない
- 上から下にしか移動できない
- 左右と上下は同じ距離だけ同時に動かして良い(左に1、下に1など)
- 左右と上下を同時に動かして良いのはxとyが同じ時だけ((A,A)の時など)
この中でもっとも少ない数で対角線の位置に移動する方法を探します。
これが最長共通部分列問題です。
_CollectionChangesに当てはめると
- 垂直への移動が挿入
- 平行への移動が削除
になります。
結果は下記になります。
| • | X | A | B | C | D |
• | S | | | | | |
X | | x | x | x | | | // S: 開始
Y | | | | x | | | // T: 目的地
C | | | | | x | |
D | | | | | | T |
// 経路:
(0,0) → (1,1) → (1,2) → (1,3) → (2,3) → (3,4) → (4,5)
これを_CollectionChangesで考えると
- (1,1) → (1,2)、(1,2) → (1,3)は２つの削除
- (1,3) → (2,3)は１つの挿入
になります。
この一つ一つの地点がEndpointであり
pathはEndpointの配列になります。
これがpathStorageプロパティになります。
pathStartIndex
_CollectionChangesが持つもう一つのプロパティで
差分計算のパスを探す開始位置を表します。
これは内部最適化のために使われ
例えばAEOSとAEFTという文字列があった場合
AEは共通なのでこの分の計算は無駄になります。
そこでpathStartIndexを見てこの無駄をスキップします。
pathStartIndex
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/Diffing.swift#L279
enum Element
internalな要素で上記の計算で見つけたパスを
CollectionDifference.Changeに変換するときに使用します。
enum Element {
case removed(Range<SourceIndex>)
case inserted(Range<TargetIndex>)
case matched(Range<SourceIndex>, Range<TargetIndex>)
}
_CollectionChanges.Element
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/Diffing.swift#L300
※ なぜRangeなのか？
上記の問題の例では一つ一つEndpointを分けて考えましたが
(1,1) → (1,2) → (1,3)は連続した平行移動で
(1,1) → (1,3)と一緒にできます。
これを表現するためにRangeとなっています。
differenceメソッドでは
このElementを一つ一つ取り出してCollectionDifference.Changeへと変換していきます。
_CollectionChangesの内部
まず中心となるinitの形です。
fileprivate
init<Source: BidirectionalCollection, Target: BidirectionalCollection>(
from source: Source,
to target: Target,
by areEquivalent: (Source.Element, Target.Element) -> Bool
) where
Source.Element == Target.Element,
Source.Index == SourceIndex,
Target.Index == TargetIndex
{
self.init()
formChanges(from: source, to: target, by: areEquivalent)
}
空のinitは下記になります。
private init() {
self.pathStorage = []
self.pathStartIndex = 0
}
formChangesメソッドでpathStorageにEndpointを追加していきます。
下記ような処理を行っています。
最初のチェック
最初のチェックとして下記の２つを行います。
- 両方のコレクションが空の場合
すぐに処理を中断し、diffrenceの結果も空になります。
- 共通の接頭辞を見つけ、かつ1つのコレクションがもう1つのコレクションの全要素を網羅している場合
上記の最短経路問題で考えると
右か下にぶつかるまで斜めに移動することができ
その後平行か垂直移動して対角線にいきます。
いくつかの例を見てイメージしてみます。
// source = ASDFO
// target = ASD
// targetはsourceの接頭辞になっています:
| • | A | S | D | F | O |
• | S | | | | | |
A | | x | | | | | // S: 開始
S | | | x | | | | // T: 目的地
D | | | | x | x | T |
↑
ここで端にぶつかって平行移動している
// 最終経路:
(0,0) → (3,3) → (3,5)
// - 3つが一致 (0,0) → (3,3)
// - ２つ削除 (FとO), (3,3) → (3,5)
// source = ASD
// target = ASDFO
// sourceがtargetの接頭辞になっています:
| • | A | S | D |
• | S | | | | // S: 開始
A | | x | | | // T: 目的地
S | | | x | |
D | | | | x | ← ここで端にぶつかって垂直移動している
F | | | | x |
O | | | | T |
// 最終経路:
(0,0) → (3,3) → (5,3)
// - ３つが一致 (0,0) → (3,3)
// - ２つ挿入 (FとO), (3,3) → (5,3)
// source = ASD
// target = ASD
// 両方同じ要素
| • | A | S | D |
• | S | | | | // S: 開始
A | | x | | | // T: 目的地
S | | | x | |
D | | | | T | ← 端にぶつかる
// 最終経路:
(0,0) → (3,3)
// - ３つが一致 (0,0) → (3,3)
上記では２か３つの要素を持ったpathStorageができます。
formChangesCore
上記の条件に合わない場合は
下記のような状態になっています。
- ２つのコレクションの要素が等しくない(byで示した条件ですべてtrueにならない)
- ２つのコレクションが空ではない
- 共通の接頭辞がある可能性がある
この際にはformChangesCoreメソッドを呼び出します。
formChangesCore
https://github.com/apple/swift/blob/a0421124f0de37d696e503c17c05afba19f74cf2/stdlib/public/core/Diffing.swift#L411
引数には２つのコレクションと等しいとみなすための条件に加えて
最初のロジックで見つけた共通の接頭辞のindexです。
これを渡すことで不要な計算をスキップします。
このメソッド内では
Greedy LCS/SES Algorithmを実装しています。
http://www.xmailserver.org/diff2.pdf
詳細は割愛しますが簡単に何をしているのかを示すと
- まずはもっとも時間がかかるように斜め移動なしでのDまでの移動手順を見つけます。
- この時点で目的地に到着したら計算を終了します。
- 到着していない場合、Dの値を一つずつ増やして再び最初から計算を開始します。
この際により最適化するために前のパスをロジックに従った形で保存しておくことで
できる限り計算の無駄をなくすようにされています。
ご興味のある方は冒頭の参照記事をご覧ください。
まとめ
Ordered Collection Diffingについて見てきました。
使う側としては非常にシンプルに使えますが
内部の複雑なアルゴリズムに支えられ
安全に効率良く差分計算を実現されていることもわかりました。
参照記事の筆者も結論で述べていますが
これはCollectionViewやTableViewでは使用しない方が良く
代わりにDiffable Data Sourcesというより最適化されたAPIが
iOS13で用意されています。
詳細は下記にまとめましたのでもしよろしければご参照ください
https://qiita.com/shiz/items/a6032543a237bf2e1d19
Swiftはまだまだ発展途上で
たくさんのプロポーサルが出てきています。
これからもどんな新しい機能が増えていくのか楽しみですね
もし間違いなどございましたら教えていただけると嬉しいです