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

Swift

Apple が提供している swift-collections を説明します。

環境&対象

以下の環境で動作確認を行なっています。

  • macOS Big Sur 11.2.3
  • Xcode 12.4
MEMO
環境として macOS と書いてますが、iOS でも同様に使用できます。

swift-collections

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

github は、こちら

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

  • Deque<Element>
  • OrderedSet<Element>
  • OrderedDictionary<Element>

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

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

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

OrderedDictionary

名前から分かる通り、順序を保存する Dictionary です。

GitHub での説明はこちら

OrderedDictionary が Dictionary と同じ点

キーがユニークであることが必要です。ユニークであることを確認するために、hash が使用されます。OrderedDictionary は、Dictionary と同様に hash table を使用して、キーがユニークであることを利用して、値を保持します。

キーには、どのような型も使えますが、Hashable に conform している必要があることも Dictionary と同じです。

OrderedDictionary が Dictionary と異なる点:同値判定

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

OrderedDictionary が Dictionary と異なる点:順序操作

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

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

順序を変更するメソッド

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)

OrderedDictionary が Dictionary と異なる点:追加されたメソッド

Dictionary では、updateValue というメソッドを使って、Value を変更することができます。(OrderedDictionary でも使えます)

OrderedDictionary には、closure を引数にとる modifyValue というメソッドが追加され、modifyValue を使っても Value を変更することができます。

modifyValue

let text = "short string"
var counts: OrderedDictionary = [:]
for character in text {
  counts.modifyValue(forKey: character, default: 0) { value in
    value += 1
  }
}

OrderedDictionary が順序を保持することとは関係なく、利便性のために追加されたメソッドのようです。

OrderedDictionary のパフォーマンス

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

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

考察

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

  • Dictionary と同様に、要素に対して ユニークなキーを割り当てる必要がある
  • Dictionary と同様に、キーによる検索を O(1) で行うことができる
  • Dictionary にない点として、要素の順番を保持してくれる

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

  • 要素に ユニークなキー を割り当てられるかどうか?
    (割り当てられなければ OrderedDictionary を効果的に使えない)
  • 順序ではなく ユニークなキー を使って アクセスする頻度が高いか?
    (高くなければ Array で十分)
  • 順序を保持している必要があるか?
    (順序不要なら、Dictionary で十分)

OrderedDictionary の実装

OrderedDictionary は、キーを OrderedSet で保持し、キーに対応づける Value は、Array で保持するような実装になっています。

まとめ:OrderedDictionary @ swift-collections

OrderedDictionary @ swift-collections
  • Apple から Swift のコレクションを拡張する swift-collections が公開されている
  • 要素の順序を保持できる Dictionary が OrderedDictionary
  • キーからの参照は、O(1) で行える

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です