Swift Digest
この記事の要点
- Swift で使えるデータ構造を拡充する新しいオープンソースパッケージ Swift Collections（swift-collections）が発表されました。Swift Algorithms や Swift Numerics と同様に、標準ライブラリへの取り込みを見据えた新機能の実験場として位置づけられています。
- 標準ライブラリは
Array・Set・Dictionaryという汎用的なデータ構造を備えていますが、問題を効率的に解いたり不変条件を保ったりするには、より多くのデータ構造があると役立つ場面があります。 - 初版では、よく要望される 3 つのデータ構造、両端キュー（
Deque）、順序付き集合（OrderedSet）、順序付き辞書（OrderedDictionary）が提供されます。
何が発表されたのか
Swift Collections は、Swift で利用できるデータ構造を拡充することに焦点を当てたパッケージです。標準ライブラリは Array・Set・Dictionary という最も基本的な 3 つの汎用データ構造を備えており、これらは幅広い用途に適し、特に currency 型として使うのに向いています。しかし、効率的に問題を解いたり不変条件を維持したりするには、より豊富なデータ構造があると有利な場面があります。Swift Collections は、より速く信頼性の高いプログラムを、より少ない労力で書けるようにすることを目指しています。
初版には、特に要望の多かった 3 つのデータ構造が含まれます。
何に使えるのか
Deque
Deque（「デック」と読み、double-ended queue の略）は Array とよく似た、順序付き・ランダムアクセス可能・ミュータブルで、整数インデックスを持つ range-replaceable なコレクションです。Array との大きな違いは、両端での挿入・削除を効率的に行える点です。これにより、先入れ先出し（FIFO）のキューが必要な場面で良い選択肢になります。両端への要素の追加・取り出しのための操作が用意されています。
var colors: Deque = ["red", "yellow", "blue"]
colors.prepend("green")
colors.append("orange")
// colors is now ["green", "red", "yellow", "blue", "orange"]
colors.popFirst() // "green"
colors.popLast() // "orange"
// colors is back to ["red", "yellow", "blue"]
Array の先頭への要素追加は線形時間ですが、Deque では定数時間で行えます。もちろん MutableCollection や RangeReplaceableCollection のおなじみのメソッドも使え、インデックスは Array と同じく先頭が常に 0 から始まります。
colors[1] // "yellow"
colors[1] = "peach"
colors.insert(contentsOf: ["violet", "pink"], at: 1)
colors.remove(at: 2) // "pink"
colors.sort()
ただし、先頭への効率的な挿入を実現するため、Deque は要素を連続メモリ上に保持することを諦めています。そのため、先頭での挿入・削除を必要としない用途では Array よりわずかに遅くなる傾向があります。すべての Array を無条件に Deque に置き換えるのは得策ではありません。
OrderedSet
OrderedSet は Array と Set を組み合わせたようなデータ構造です。Hashable プロトコルに適合する任意の要素型で作成できます。
let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]
Array のように要素をユーザー指定の順序で保持し、ランダムアクセスでの走査を効率的に行えます。同時に Set のように各要素が一度しか現れないことを保証し、メンバーシップ判定を効率的に行えます。
buildingMaterials.append("straw") // (inserted: false, index: 0)
buildingMaterials.contains("glass") // false
buildingMaterials.append("glass") // (inserted: true, index: 3)
// buildingMaterials is now ["straw", "sticks", "bricks", "glass"]
メンバーシップ判定は Array では線形時間ですが、OrderedSet では定数時間です。要素は内部で通常の配列値として保持されており、elements プロパティでわずかなオーバーヘッドで取り出せます。Array を取る関数へ渡したいときに便利です。
buildHouses(buildingMaterials) // error
buildHouses(buildingMaterials.elements) // OK
また SetAlgebra 適合が必要な場面では、SetAlgebra に適合する効率的な unordered view を unordered プロパティで得られます。OrderedSet 自体は、メンバーの一意性と順序を考慮した等価判定のため、SetAlgebra には完全には適合しません。
blowHousesDown(buildingMaterials) // error: OrderedSet<String> does not conform to SetAlgebra
blowHousesDown(buildingMaterials.unordered) // OK
OrderedSet は、ランダムアクセス走査用のメンバー配列と、その配列へのインデックスを格納したハッシュテーブルを組み合わせて実装されています。ハッシュテーブルに格納するインデックスは通常の Int より少ないビット数で表現できることが多いため、OrderedSet は普通の Set よりメモリ使用量が少なくなることもあります。
OrderedDictionary
OrderedDictionary は、要素の順序が重要な場合や、コレクション内のさまざまな位置の要素へ効率的にアクセスしたい場合に、Dictionary の代わりとして役立ちます。Hashable に適合する任意のキー型で作成できます。
let responses: OrderedDictionary = [
200: "OK",
403: "Forbidden",
404: "Not Found",
]
Dictionary と同じくキーによる subscript で値の参照・追加を効率的に行えます。subscript のセッターで新しいエントリを追加すると末尾に追加されるため、デフォルトでは要素は挿入順に保持されます。
responses[200] // "OK"
responses[500] = "Internal Server Error"
OrderedDictionary は先頭を常に 0 とする整数インデックスを持ちます。キーによる subscript とインデックスによる subscript の曖昧さを避けるため、Collection には直接適合せず、代わりにキーと値のペアに対する elements ビューを提供します。
responses[0] // nil（キーによる subscript）
responses.elements[0] // (200, "OK")（インデックスによる subscript）
標準の Dictionary と同様に軽量な keys ビューと values ビューも提供され、同じインデックスをすべてのビューで使い回せます。
if let i = responses.index(forKey: 404) {
responses.keys[i] // 404
responses.values[i] // "Not Found"
responses.remove(at: i + 1) // (500, "Internal Server Error")
}
OrderedDictionary は内部的に、キーの OrderedSet と、対応する値を持つ通常の Array から構成されます。どちらもわずかなオーバーヘッドで取り出せるため、特定の型を期待する関数との相互運用に効率的です。
標準ライブラリとの関係・今後の位置づけ
発表時点で示されていた今後の構想であり、実現を約束するものではありません。
標準ライブラリには、豊富で実用的な汎用データ構造を備えさせたいという狙いがあります。Swift Numerics や Swift Algorithms と同様、Swift Collections は、新しいデータ構造の実装を正式に Swift Evolution へ提案する前に、（比較的）低コストに検証する場として機能します。パッケージとして使った経験が最終的なレビュー議論の材料となり、設計上の問題を確定前に修正する機会も得られます。
標準ライブラリは ABI 安定であるため、データ構造のどの部分を @frozen にするか、どのメソッドを @inlinable にして frozen な内部に触れさせるか、といった設計に多くの時間を要します。Swift Collections は単なるデータ構造の集まりではなく、こうした ABI 設計のノウハウを学ぶ場であり、正しさと効率の高い基準を満たすための高度なツールキットでもあります。ただしこれは Swift Evolution プロセス自体の変更ではなく、十分に練られた pitch はこれまでどおり検討されます。
このパッケージが当面対象とするのは、C++ の containers ライブラリや Java の collections フレームワークにあるような、実用的でプロダクション品質のデータ構造です。収録の候補となるには、現実の Swift コードの性能や正しさを目に見えて改善し、その実装戦略が現代の計算機アーキテクチャと Swift の性能特性を踏まえている必要があります。収録基準は高く、信頼性・実行時性能・メモリオーバーヘッドの観点から評価されます。一方で、標準ライブラリの既存型に対して価値が乏しいデータ構造（連結リストや赤黒木など）は対象外とされています。
Swift Collections は完全なオープンソースプロジェクトで、GitHub 上で開発されています。議論は Swift フォーラムの Collections カテゴリで行えます。