BT

最新技術を追い求めるデベロッパのための情報コミュニティ

寄稿

Topics

地域を選ぶ

InfoQ ホームページ ニュース Swift CollectionsはSwiftに新しいデータ構造をもたらす

Swift CollectionsはSwiftに新しいデータ構造をもたらす

原文(投稿日:2021/04/10)へのリンク

Swift Collectionsは、Swiftプログラマーが利用できるデータ構造の選択肢を広げることを目的とした新しいオープンソースパッケージである。標準ライブラリで提供されるものとは別に提供される。初期バージョンでは、両端キュー順序セット順序辞書を提供する。

両端キューの略であるDequesは配列に似ているが、[FIFOキュー](https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics))のように、最初と最後の両方で効率的な挿入と削除をサポートする。特に、SwiftのエンジニアであるKaroy Lorentey氏のベンチマークによると、Dequeでは要素を先頭に追加することは定数時間操作であり、32要素のコレクションサイズで始まるArrayに対する同じ操作よりもパフォーマンスが大幅に向上する。ただし、これは、連続していないバッファにdeque要素を割り当てることで実現される。そのため、通常の操作は配列よりもわずかに遅くなる。

prependメソッドを使用して、両端キューの先頭に新しい要素を挿入し、appendメソッドを使用して最後に要素を挿入できる。同様に、popFirstpopLastを使用して、両端キューの端から要素をポップできる。

var elements = Deque["e1", "e2"]

elements.prepend("e0")  // -> ["e0", "e1", "e2"]
elements.append("e3")  // -> ["e0", "e1", "e2", "e3"]

let e0 = elements.popFirst()
let e3 = elements.popLast()

OrderedSetは、各要素が一意であることを保証する。そして、集合にappendされた順序を維持しながら、containsを使用して効率的なメンバーシップテストを提供する。Lorenteyのベンチマークによって、containsを使うと、約64要素で始まる順序付けされていないSetよりもパフォーマンスが大幅に向上することが示されている。OrderedSetは、.elementsプロパティを使用してArray引数を期待する関数に簡単に渡すことができる。SetAlgebra準拠が必要な場合、.unorderedプロパティは、集合の要素の順序付けられていないビューを提供する。

Swift Collectionsに存在する3番目のコレクションはOrderedDictionaryである。これは、辞書に関して望ましいプロパティをすべて保持する。要素がユーザ定義の順序のままであることを保証しながら、定数時間の挿入やアクセスを提供する。繰り返しになるが、定数時間の操作が享受できる一方で、OrderedDictionaryに対するその定数は、順序付けされていないDictionaryの定数よりもわずかに高くなる。OrderedDictionaryは、キーのOrderedSetと要素の通常のArrayで構成されいる。そして、その両方に.keysプロパティと.elementsプロパティを使って効率的にアクセスできる。

Swift Collectionsは、Swift NumericsパッケージおよびSwift Algorithmsパッケージと性質や意図が似ている。それらはすべて、標準ライブラリで利用できないデータ構造を提供しようとするものである。これらは、公式のSwiftの進化プロセスを通して、標準ライブラリに最終的に含まれる可能性のある。

Swift CollectionsはGitHubで入手できる。貢献は大歓迎である。ただし、信頼性、パフォーマンス、メモリ使用量に関する厳しい基準を満たす必要がある。このようにLorentey氏は述べている。

この記事に星をつける

おすすめ度
スタイル

特集コンテンツ一覧

BT