swift-collectionsで学ぶデータ構造

swift-collectionsは、Swiftプログラミング言語を使って一般的に使用されるデータ構造の実装を提供するApple製のオープンソースパッケージです。これは、場合によって標準ライブラリよりもっと効率的に使いやすいものです。今回はswift-collectionsにあるデータ構造に対して簡単に紹介します。

BitSetとBitArray

BitSet は、特定のビットがセットされているかどうかを効率的にチェックすることができます。例えば、特定の要素が存在するかどうかを追跡するのに使えます。

var bitSet = BitSet()
bitSet.insert(2)
bitSet.insert(4)

print(bitSet.contains(2)) // true
print(bitSet.contains(3)) // false

BitArray は、ビットの配列を管理するのに役立ちます。各ビットは true または false の状態を持ちます。

var bitArray = BitArray(repeating: false, count: 5)
bitArray[2] = true
bitArray[4] = true

print(bitArray[2]) // true
print(bitArray[3]) // false

Deque

Deque は他の言語でもよく出てきます。両側から要素の挿入と削除を効率できにサポートします、特に配列の開始また終了から頻繁に要素の追加また削除が発生する場合はDequeを使うべきだと思います。

参照：https://favtutor.com/blogs/deque-python

実際Dequeで最初の要素を削除することで普通の配列で最初の要素を削除するときの効率を比べみましょう

var list = Array(repeating: 0, count: 100000)
while list.count > 0 {
    list.removeFirst()
}
// 0.805秒かかります

var list = Deque(Array(repeating: 0, count: 100000))
while list.count > 0 {
    list.removeFirst()
}
// 0.017秒しかかかりません！

通常のリストで最初の要素を削除もしくは挿入の場合、その後の要素を移動する必要があります、そのためDequeよりもっと時間がかかります、Dequeがリングバッファを使うことで要素の移動が発生しないので単純なリストより最初の要素を削除するのは速いです。

Heap

続いてHeapを紹介します。最小最大ヒープとして実装されたこのデータ構造は、優先度キューとして使用できます。最小または最大の要素に効率的にアクセスできるため、特定の順序で要素を処理する必要があるタスクに理想的です。現在ではswift-collectionsではFloyd氏の方法で配列を利用してHeapを構築してます。

参照：CSE 373 20au, Lesson 13 Video 3: Floyd's buildHeap Algorithm
　　　　　　
実際に使うシーンに関して例えば、複数の優先度を持ってるタスクを順番で挿入していつも優先度が高いタスクを取り出すためHeapを使えます。

struct Task: Comparable {
    let id: UUID
    let priority: Int
    
    // priority数値が小さい方優先度が高い
    static func < (lhs: Task, rhs: Task) -> Bool {
        lhs.priority > rhs.priority
    }
}

var tasks = Heap<Task>()
tasks.insert(.init(id: "TaskA", priority: 3))
tasks.insert(.init(id: "TaskB", priority: 2))
tasks.insert(.init(id: "TaskC", priority: 0))
        
print(tasks.max?.id) // TaskC

tasks.popMax() // TaskCがHeapから取り出した
print(tasks.max?.id) // TaskB

tasks.insert(.init(id: "TaskD", priority: 0)) // 優先度0のTaskDを挿入
print(tasks.max?.id) // TaskD 

Heapに新しい要素を挿入する際にいつもソート順で挿入されたのでこれは便利です

OrderedSet

セットの一意性の制約と配列の順序付けの特徴を組み合わせたOrderedSetは、要素が一意であることを保証しつつ、特定の順序を維持します。セットの特性と要素の順番の両方の保証が必要な場合はOrderedSetを使って良いです。例えば重複なものを取り除く同時にもとの順番を維持したい時

let arrayWithDuplicates = ["apple", "orange", "banana", "apple", "orange"]
let uniqueOrderedSet = OrderedSet(arrayWithDuplicates)

print(Array(uniqueOrderedSet))
// ["apple", "orange", "banana"]

そのほかには例えばランキングシステムの実装ではランキングでの要素の唯一性を持つながら、ランキング中の要素の順番をもつことができます。

OrderedDictionary

標準辞書の順序付き変種であるOrderedDictionaryは、要素の挿入順序を追跡できます。これにより、キーによる効率的な要素をアクセスが可能です同時にキーと値の順序付きトラバースを可能にします。

例えば、アルファベットの順番で人の電話番号を記録する際に、OrderedDictionary を使うことができます。

var records = OrderedDictionary<String, String>()

records["Alien"] = "1"
records["Banana"] = "2"
records["Cookie"] = "3"

// Cookieの電話番号を変更
records["Cookie"] = "6"

/**
Alien: 1
Banana: 2
Cookie: 6
**/

TreeSetとTreeDictionary

TreeSetとは同じコレクションの異なるスナップショットを比較し、共有コピーを変更する際に最適化された、一意な要素の順序付けされていないコレクションです。普段のSetと同じ機能を持ってますけど、でもTreeSetの方はコピーしたものを編集後、もとのデータと比べる際に最適されてます

var set = TreeSet(0 ..< 10_000)
let copy = set
set.insert(20_000) // 挿入の時間複雑度がO(log(n))
let diff = set.subtracting(copy) // 違いものを見つけるの時間複雑度も同じO(log(n))！
// `diff`が 20_000だけを持ってます

TreeDictionary はTreeSetと同じ特徴が持っています、ただ対象が単純なコレクションではないキーとそれに関連する値の順序付けされていないコレクションです

var d = TreeDictionary(uniqueKeysWithValues: (0 ..< 10_000).map { ($0, 2 * $0) })
let copy = d
d[20_000] = 42 // 挿入の時間複雑度がO(log(n))
let diff = d.keys.subtracting(copy.keys) // 違いものを見つけるの時間複雑度も同じO(log(n))！
// `diff`がキー 20_000と関連する値42を持ってます

SortedSetとSortedDictionary

こちらのデータ構造はまだ正式にリリースされてないけど、SPMでswift-collectionsのmainブランチを指定すれば使えます。

SortedSetとSortedDictionaryは、要素またはキーと値のペアが順序付けされたコレクションです。これらのデータ構造は、要素やキーの追加、削除、検索を効率的に行うために、内部的にバランスの取れた木構造を使用しています。これにより、コレクションの状態を容易に維持し、順序付けられた状態での高速なアクセスを実現します。

SortedDictionaryは要素を挿入する同時にキーをソートされた順序を維持できます、また電話番号を例として説明します

var records = SortedDictionary<String, String>()

records["Dainel"] = "000"
records["Bob"] = "123"
records["Alice"] = "456"

print(records)
// [Alice: 456, Bob: 123, Dainel: 000] キーが正しいアルファベット順で並んでます

SortedDictionaryとSortedSetがBTreeを使って実装されるので、要素をアクセスするときの時間複雑度がO(log(n))、普段のSetとDictionaryに比べると遅いので実際のシチュエーションによって判断して使って良いと思います。

以上swift-collectionsにあるデータ構造を簡単に紹介しました、興味ある人是非自分で使ってみてください！