[Swift] Swift-Collections の紹介 (OrderedSet)

環境＆対象

swift-collections

Apple が github 経由で公開しているライブラリを使うことで、集合を表す要素（コレクション）を ３つ 追加することができます。

github は、こちら。

Swift Package Manager 経由で設定することで、以下の３つのコレクションを使用することができます。

• Deque＜Element＞
• OrderedSet＜Element＞
• OrderedDictionary＜Element＞

それぞれ、Generics を使用して定義されていますので、対象要素としてさまざまな型を保持することができます。

公開されたデータを見ながら、どのコレクションをどのような時に使うと効率的なのかを考察していきます。

なお、Swift.org の Blog でも説明されています。

Set

OrderedSet の説明の前に、Set の概要を説明します。

Apple Document での Set の説明は、”An unordered collection of unique elements” です。

Set は、以下のような特徴を持つコレクションです。

• 順番を持たない
• 重複しない（同一要素をコレクション内に複数持たない）
• ある要素がコレクションに含まれているかどうかを効率よく判定できる

OrderedSet

名前が意味するように、順序を保存する Set です。

GitHub での説明はこちら。

OrderedSet は、上に挙げた Set の １番目の特徴を持たずに、２、３番目の特徴を持つコレクションです。

OrderedSet が Set と同じ点：Hashable

OrderedSet は、Set と同じように hash を使用して、要素を管理します。ですので、Set の要素が Hashable に conform する必要があるのと同様に、OrderedSet の要素も、Hashable に conformm する必要があります。

OrderedSet が Set と似た点：SetAlgebra

集合演算のためのプロトコルに SetAlgebra がありますが、Set と同様に OrderedSet も SetAlgebra プロトコルにあるようなメソッドが実装されています。
しかし、全てのメソッドが実装されているわけではなく、いくつかのメソッドは実装されていません。（ですので、SetAlgebra に conform しているわけではなりません。）

演算に対して、OrderedSet が保持している順番の情報も極力 使用するようになります。

let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]
buildingMaterials.intersection(["brick", "straw"]) // ["straw", "brick"]

しかし、いくつかのメソッドは 順番を考慮しません。

let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]
let moreMaterials: OrderedSet = ["bricks", "glass", "sticks", "straw"]
buildingMaterials.isSubset(of: moreMaterials) // true

例えば、intersection の出力は 順番を保持していますが、isSubset(of:) の出力は、順番を保持していません。

OrderedSet に実装されていない SetAlgebra メソッド

func insert(Self.Element) -> (inserted: Bool, memberAfterInsert: Self.Element)
func update(with: Self.Element) -> Self.Element?

上記の代わりに以下のような順序を考慮したメソッドが実装されています。

func insert(_ item: Element, at index: Index) -> (inserted: Bool, index: Int)
func append(_ item: Element) -> (inserted: Bool, index: Int)
func update(at index: Int, with item: Element) -> Element
func updateOrAppend(_ item: Element) -> Element?

Set との協調

Set は SetAlgebra に conform していますが、OrderedSet は、conform していません。

ケースによっては不便になることもありますので、便利なメソッドが用意されています。

var a: OrderedSet = [0, 1, 2, 3]
let b: OrderedSet = [3, 2, 1, 0]
a == b // false
a.unordered == b.unordered // true

func frobnicate(_ set: S) { ... }
frobnicate(a) // error: `OrderedSet` does not conform to `SetAlgebra`
frobnicate(a.unordered) // OK

Unordered で返される要素は、mutable で insert された要素は、最後の要素として追加されます。

let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]
buildingMaterials.unordered.insert("glass") // => inserted: true
// buildingMaterials is now ["straw", "sticks", "brick", "glass"]

OrderedSet が Set と異なる点：同値判定

OrderedSet は、与えられた要素の順番を保持しますので、OrderedSet 同士を比較する時にも、保持している要素だけでなく その順番も一致していないと OrderedSet として一致していることになりません。

OrderedSet が Set と異なる点：順序操作

OrderedSet に要素が追加される時には、一番最後の要素として追加されます。

OrderedSet では、順序を変更するために以下のメソッドを使用することができます。

func swapAt(_ i: Index, _ j: Index)
func partition(by predicate: (Element) throws -> Bool) -> rethrows Index
func sort() where Element: Comparable
func sort(by predicate: (Element, Element) throws -> Bool) rethrows
func shuffle()
func shuffle(using generator: inout T)

OrderedSet が Set と異なる点：Random-access

OrderedSet が保持する順番は常に、0 から開始されます。このインデックスを使用して要素にアクセスしたり、要素を使ってインデックスを取得 することもできます。

let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]
buildingMaterials[1] // "sticks"
buildingMaterials.firstIndex(of: "bricks") // 2

しかし、同一要素は １つしか持てないために、MutableCollection　や RangeReplaceableCollection に conform はしていません。以下のように 一部のメソッドが実装されています。

// Permutation operations from MutableCollection:
func swapAt(_ i: Int, _ j: Int)
func partition(by predicate: (Element) throws -> Bool) -> rethrows Int
func sort() where Element: Comparable
func sort(by predicate: (Element, Element) throws -> Bool) rethrows
func shuffle()
func shuffle(using generator: inout T)
func reverse()

// Removal operations from RangeReplaceableCollection:
func removeAll(keepingCapacity: Bool = false)
func remove(at index: Int) -> Element
func removeSubrange(_ bounds: Range)
func removeLast() -> Element
func removeLast(_ n: Int)
func removeFirst() -> Element
func removeFirst(_ n: Int)
func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows

// 
func reserveCapacity(Int) // but OrderedSet does not provide capacity property

Array との協調

OrderedSet から順番含め要素を取得することができます。

func pickyFunction(_ items: Array)

var set: OrderedSet = [0, 1, 2, 3]
pickyFunction(set) // error
pickyFunction(set.elements) // OK

elements に対しての操作も 元の OrderedSet の操作になります。(別変数にコピーする等を行うと、copy-on-write が発生し、元の OrderedSet への操作にはならなくなります）

また、Array 相当に変換しての操作になるため、要素がユニークであることを検査するためのコストが余計に発生し、OrderedSet へ直接操作することに対してのオーバーヘッドが発生します。

OrderedSet のパフォーマンス

パフォーマンスの考え方としては、Set と同様と説明されています。つまり、hash値の設計による計算量が支配的です。

Hashable の ベストプラクティス に従って実装されている時には、キーを使った参照は、O(1) で実行されるように実装されています。

考察

OrderedSet は、以下のような特徴をもちます。

• 重複を持たないが、順序は保持するコレクション
• Set が conform する SetAlgebra のメソッドの多くを実装する。準拠しないメソッドについては代替メソッドが用意されているため、実質 SetAlgebra 準拠相当。
• elements メソッドを使うことで Array としても使用できる。（実際に OrderedSet の内部実装の一部は Array を使用していてその Array に elements でアクセスできる）

既存のコレクションを OrderedSet に置き換えるかどうかは以下の点が検討ポイントになりそうです。

• 要素の重複チェックを効率的に行いたいかどうか？
  (重複しないならば Array でよい)
• 順序を保持している必要があるか？
  （順序不要なら、Set で十分）

OrderedSet の実装

OrderedSet は、Array ハッシュテーブル の組み合わせで実装されています。ハッシュテーブルから Array のインデックス が取得できます。
Array のサイズから ハッシュテーブルが保持すべきインデックスの範囲を調整することが可能で、インデックスを Int よりも少ないビット数にすることで Set よりも最適化できる可能性があります。

まとめ：OrderedSet @ swift-collections

説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。

関連記事:

[Swift] Swift-Collections の紹介 (Deque) [Swift] Swift-Collections の紹介 (OrderedDictionary) [Swift][SwiftUI] actor を使って、LifeGame を作る(その１: actor でモデルを作る) [Swift] AtCoder を UnitTest しつつ解く