Meet the Swift Algorithms and Collections packages

ハイライト

Apple は、Swift Algorithms と Swift Collections という 2 つのオープン ソース パッケージをリリースしました。これにより、開発者は新しいシーケンス アルゴリズム、デキュー、順序付きセット、および順序付き辞書を使用できるようになり、これらの API を将来の標準ライブラリ機能のインキュベーターとして使用できるようになります。

主要内容

チャット アプリには、この種のコードが含まれることがよくあります。ユーザーがメッセージの数行を選択すると、対応するメッセージを取得したいとします。Message;ユーザーが画像をクリックしたら、メッセージから添付ファイルを収集する必要があります。詳細ページには最後の 6 枚の写真が表示されます。最も直接的な書き方は、forループ、一時配列、if let、break。

これらのループは機能しますが、制御フロー内にその意図が隠されています。コードを読む人は、変換、フィルタリング、フラット化、または最初のいくつかの要素の取得だけを行うのかを知るために、ループ全体を読む必要があります。また、ループでは、容量の予約や遅延計算などのパフォーマンスの詳細が見逃される傾向があります。

Swift の標準ライブラリにはすでにmap、compactMap、flatMap、prefix、suffix、reversedこれらのアルゴリズム。 Swift アルゴリズムは、スライディング ウィンドウ、隣接要素、チャンキング、条件によるグループ化など、標準ライブラリでまだカバーされていないパターンを補完し続けます。

Apple は Swift Collection もリリースしています。 Swift 標準ライブラリには長い間、データ構造の一般的なカテゴリが 3 つしかありませんでした。Array、Set、Dictionary。これらは一般的な境界タイプには適していますが、キュー、順序付けされた一意のリスト、順序付けされたキーと値のテーブルなどのシナリオでは、問題により近いデータ構造が必要です。

Swift コレクションを活用Deque、OrderedSet、OrderedDictionary。これらは、Swift コレクションの値のセマンティクスとコピーオンライトの動作を維持しながら、標準ライブラリの欠落している操作モデルを埋めます。

原始的なループからアルゴリズムの語彙まで

チャット アプリのコードでは、多くのループに実際に名前が付いています。回線転送メッセージを選択、はいmap。空ではない添付ファイルを収集します。はいcompactMap。メッセージは複数のトランスクリプト項目を生成し、それらをフラット化します。はいflatMap。

これらの名前を使用すると、コードの焦点は「ループ方法」から「このステップで何を行うか」に変わります。これは Swift アルゴリズムの位置づけでもあります。まず、欠落している共通パターンをオープンソース パッケージに組み込み、開発者がそれを使用し、その後コミュニティが協力して標準ライブラリに含めるのに適しているかどうかを検証します。

一般的なコレクションから適切なデータ構造へ

Array添え字によるアクセスには最適ですが、先頭に要素を挿入するには既存の要素を移動する必要があります。キュー、タスクのスケジュール設定、チャット ドラフトの取り消しスタックなどのシナリオでは、両端からスタックの挿入と削除が行われることがよくあります。Arrayコストは高めです。

Set一意性は保証されますが、順序は保証されません。ユーザーが手動で並べ替えたToDoリストやタグリスト、お気に入りなどは、「独自の要素」と「安定した順序」の両方を満たす必要があります。これはOrderedSet位置。

Dictionaryキーによって値をすばやく検索できますが、キーと値のペアの順序はコア セマンティクスとして公開されません。フィールド、パラメータ、設定項目を挿入順に表示する必要がある場合、OrderedDictionaryキーの検索と保存の順序を同じタイプに置きます。

詳細

標準ライブラリ アルゴリズム: ループを読み取り可能な操作に書き換える

（01:00）map入力コレクション内の各要素を別の値に変換するために使用されます。講義内の例は、テーブルの選択された行からのものです。indexPathsForSelectedRowsそこに保存されているのはインデックス パスであり、アプリは対応するメッセージを取得する必要があります。

// Raw loop:
var selectedMessages: [Message] = []
for indexPath in indexPathsForSelectedRows {
    selectedMessages.append(messages[indexPath.row])
}

// Using `map` makes this clearer and faster.
indexPathsForSelectedRows.map { messages[$0.row] }

キーポイント:

• selectedMessages元のループ内の一時配列です。
• for indexPath in indexPathsForSelectedRows選択した行に 1 つずつアクセスします。
• messages[indexPath.row]行番号に従って対応するものを取得しますMessage。
• map「各インデックスパスをメッセージに変換する」を直接表現します。
• スピーチでは次のように述べられました。map容量は、元のループでの配列の拡張によって生じる中間割り当てを避けるために予約されます。

（01:36）compactMap「nil をフィルターして解凍する」という一般的なパターンを処理します。チャット アプリでは、メッセージに添付ファイルがある場合とない場合があります。

// Raw loop:
var attachments: [Attachment] = []
for message in messages {
    if let attachment = message.attachment {
        attachments.append(attachment)
    }
}

// The above is just a `map` and a `filter`.
messages
    .filter { $0.attachment != nil }
    .map { $0.attachment! }

// This pattern is so common we have a special name and algorithm for it.
messages.compactMap { $0.attachment }

キーポイント:

• attachments存在するすべての添付ファイルを収集します。
• if let attachment = message.attachment空ではない添付ファイルのみが処理されます。
• filterまず、空の添付ファイルを含むメッセージをフィルターで除外します。
• map次に、オプションのアクセサリを強制的に開梱します。
• compactMapフィルタリングと解凍を 1 つのステップで組み合わせて手書きを避ける!。

（02:06）flatMap「1対多の変換」を処理します。メッセージによって複数のトランスクリプト項目が生成される場合があります。最初ならmap、結果は配列内の配列になります。

extension Message {
    func makeMessageParts() -> [TranscriptItem]
}

messages // [Message]
    .map { $0.makeMessageParts() } // [[TranscriptItem]]
    .joined() // [TranscriptItem]

// This pattern is so common that we have another special kind of map for it.
messages // [Message]
    .flatMap { $0.makeMessageParts() }  // [TranscriptItem]

キーポイント:

• makeMessageParts()1つ置きますMessage複数に分割TranscriptItem。
• map結果は[[TranscriptItem]]、各メッセージは内部配列に対応します。
• joined()内部配列をフラット セットに連結します。
• flatMap「変換後に平坦化する」という直接的な表現。

遅延アダプター: アルゴリズム チェーンをオンデマンドで計算させます

(03:00) 詳細ページには最新の 6 枚の写真のみが必要です。元のループは逆方向に移動し、タイプ、カウントを決定し、6 に達した後に終了します。アルゴリズム チェーンはこれらのステップを分解することができます。

// Raw loop:
var photos: [PhotoItem] = []
for item in transcript.reversed() {
    if let photo = item as? PhotoItem {
        photos.append(photo)
        if photos.count == 6 {
            break
        }
    }
}

// The above can be expressed more concisely by chaining together algorithms.
transcript
    .reversed() // [TranscriptItem]
    .compactMap { $0 as? PhotoItem } // [PhotoItem]
    .prefix(6) // [PhotoItem]

// This gives us more flexibility to express this code more clearly.
transcript
    .compactMap { $0 as? PhotoItem } // [PhotoItem]
    .suffix(6) // [PhotoItem]
    .reversed() // [PhotoItem]

キーポイント:

• transcript.reversed()新しいものから古いものまで横断します。
• compactMap { $0 as? PhotoItem }写真アイテムのみを保持し、型変換が完了します。
• prefix(6)最初の6枚の写真を撮ります。
• 書くもう 1 つの方法は、最初にすべての写真を撮ることですsuffix(6)、またreversed(), 「最後の6枚の写真を逆順に表示する」という考え方に近いです。

(04:19) アルゴリズム チェーンは、各ステップで必ずしも配列を作成するとは限りません。joined()戻るFlattenSequence、これは遅延アダプター (遅延アダプター) であり、作成コストは非常に低く、要素はオンデマンドで処理されます。

extension Message {
    func makeMessageParts() -> [TranscriptItem]
}

messages
    .map { $0.makeMessageParts() } // [[TranscriptItem]]
    .joined() // FlattenSequence<[[TranscriptItem]]>

キーポイント:

• map各メッセージに対応する項目配列を生成します。
• joined()戻るFlattenSequence。
• FlattenSequence基になるコレクションをラップし、アクセス要件に基づいて要素を平坦化します。
• 講演では、このタイプのラッパーを遅延アダプターと呼んでいます。

(04:58) クロージャを使用したアルゴリズムの追加.lazy、これにより、map、filter、compactMapこのような操作は遅延して実行されます。

transcript
    .lazy // LazySequence<[TranscriptItem]>
    .compactMap { $0 as? PhotoItem } // LazyCompactMap<[TranscriptItem], PhotoItem>
    .suffix(6) // LazyCompactMap<ArraySlice<TranscriptItem>, PhotoItem>
    .reversed() // ReversedCollection<LazyCompactMap<ArraySlice<TranscriptItem>, PhotoItem>>

キーポイント:

• .lazy後続のアルゴリズム チェーンをオンデマンド コンピューティング モードに切り替えます。
• compactMap写真配列はすぐには生成されなくなりました。
• suffix(6)最後の 6 つの結果のみを考慮します。
• reversed()逆方向表示に戻ります。

(05:48) 最終的に本当に配列が必要な場合は、次を使用しますArray(...)結果を収集します。講演では、繰り返し走査されるトランスクリプトについては、編集モードに入ったり、画像をクリックしたり、詳細ページを開くたびに再計算されるのを避けるために、最終的に配列として保存することがより適切であると強調しました。

Array(
    transcript
        .lazy
        .compactMap { $0 as? PhotoItem }
        .suffix(6)
        .reversed()
)

キーポイント:

• Array(遅延結果の配列への具体化を開始します。
• transcript.lazy必要に応じて中間ステップを実行します。
• compactMap写真アイテムをフィルタリングして変換します。
• suffix(6)最後の6枚の写真を撮ります。
• reversed()表示順序を調整します。

Swift アルゴリズム: ウィンドウ、隣接要素、タイル

(07:13) Swift Algorithms によって提供windows(ofCount:)。スライディングウィンドウを返します。各ウィンドウは、基礎となるコレクションのサブシーケンスです。講義中の例では、ArraySlice、中間割り当てを避けるため。

import Algorithms

let x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for window in x.windows(ofCount: 3) {
    print(window)
}

// Prints [0, 1, 2]
// Prints [1, 2, 3]
// Prints [2, 3, 4]
// Prints [3, 4, 5]

キーポイント:

• import AlgorithmsSwift アルゴリズム パッケージの紹介。
• x走査される配列です。
• windows(ofCount: 3)長さ 3 の重複するウィンドウを生成します。
• window元のコレクションの連続したスライスです。
• 隣接するウィンドウは要素を共有します。[0, 1, 2]後ろにあるのは[1, 2, 3]。

(07:30) 長さ 2 のウィンドウが一般的であるため、パッケージは以下を提供しますadjacentPairs()。これはタプルを返し、前後の 2 つの要素へのアクセスはより簡単です。

import Algorithms

let x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for (prev, next) in x.adjacentPairs() {
    print((prev, next))
}

// Prints (0, 1)
// Prints (1, 2)
// Prints (2, 3)
// Prints (3, 4)

キーポイント:

• adjacentPairs()隣接する要素のペアを反復処理します。
• (prev, next)前と次の要素を直接分解します。
• 日付間隔、傾向の変化、連続的な繰り返しの検出など、隣接する値を比較するのに適しています。

（07:45）chunks(ofCount:)固定サイズでグループ化します。ウィンドウとは異なり、ブロックは重なりません。

import Algorithms

let x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

for chunk in x.chunks(ofCount: 3) {
    print(chunk)
}

// Prints [0, 1, 2]
// Prints [3, 4, 5]
// Prints [6, 7, 8]
// Prints [9]

キーポイント:

• chunks(ofCount: 3)3 要素ごとにセットを生成します。
• それぞれchunk基礎となるコレクションのサブシーケンスです。
• 最後のグループに含まれる要素が 3 つ未満の場合、残りの要素が含まれます。

（08:49）chunkedカスタム条件でグループ化することもできます。講義では、これを使用してチャット レコードにタイムスタンプを挿入します。隣接するトランスクリプト項目間の間隔が 1 時間未満の場合、それらは同じグループに配置されます。グループ間に挿入DateItem。

import Algorithms

extension Message {
    func makeMessageParts() -> [TranscriptItem]
}

transcript = Array(
    messages
        .lazy
        .flatMap { $0.makeMessageParts() }
        .chunked { $1.date.timeIntervalSince($0.date) < 60 * 60 }
        .joined { DateItem(date: $1.first!.date) }
)

キーポイント:

• messages.lazyメッセージ配列の処理が遅延しました。
• flatMap { $0.makeMessageParts() }メッセージをトランスクリプト アイテムのフラット ストリームに変換します。
• chunked { ... }隣接する 2 つの要素を受け取る$0そして$1。
• $1.date.timeIntervalSince($0.date) < 60 * 602 つの項目間の間隔が 1 時間未満であることを示します。
• joined { DateItem(date: $1.first!.date) }隣接するグループ間の次のグループの最初の日付に基づいてタイムスタンプを挿入します。
• Array(...)その後の二重カウントを避けるために、最終的な記録を保存します。

Swift コレクション: Deque は両端での操作に適しています

（14:56）Deque両端キュー（両端キュー）です。末尾からの追加と先頭からの削除だけでなく、先頭からの挿入と末尾からの削除もサポートされています。

import Collections

var queue: Deque = ["A", "B", "C"]

queue.append("D")
queue.append("E")
queue.removeFirst()  // "A"
queue.removeFirst()  // "B"

queue.prepend("F")
queue.prepend("G")
queue.removeLast()   // "E"
queue.removeLast()   // "D"

キーポイント:

• import CollectionsSwift Collections パッケージの紹介。
• var queue: Deque = ["A", "B", "C"]配列リテラルを使用して両端キューを作成します。
• appendキューの最後から要素を追加します。
• removeFirstキューの先頭から要素を削除します。
• prependキューの先頭から要素を追加します。
• removeLastキューの最後から要素を削除します。

（15:46）DequeAPI は次のようなものに近いですArray。それは準拠しますRandomAccessCollection、MutableCollectionそしてRangeReplaceableCollectionを使用すると、整数の添字によって範囲にアクセス、変更、挿入できます。

import Collections

var items: Deque = ["D", "E", "f"]
print(items[1])  // "E"
items[2] = "F"
items.insert(contentsOf: ["A", "B", "C"], at: 0)
print(items[1])  // "B"

キーポイント:

• items[1]要素を位置ごとに読み取ります。
• items[2] = "F"添字を付けて要素を変更します。
• insert(contentsOf:at:)指定された位置に要素を挿入します。
• at: 0先頭に挿入することを示します。
• スピーチノート、Dequeこれにより、ストレージ バッファーが境界をバイパスするため、最初の挿入では既存の要素を移動する必要がなく、時間はほぼ一定になります。

（18:39）Deque途中の範囲を削除する場合、前半または後半の要素を移動して穴を埋めるように選択できます。講演では、ランダムな位置の削除は平均して 2 倍高速であると結論付けられました。

import Collections

var items: Deque = ["A", "B", "C", "D", "E", "F"]
items.removeSubrange(1 ..< 3)

キーポイント:

• items初期状態では 6 つの要素が含まれています。
• 1 ..< 3添え字 1 から添え字 3 までの範囲を表します。
• removeSubrange消去"B"そして"C"。
• Deque削除された穴を閉じるために、小さい側を移動することを選択できます。

OrderedSet: 一意性と順序が同時に確立される

(19:33) 標準Set要素は一意であることが保証されていますが、要素の順序は意味がありません。同じ要素を含む 2 つのセットが異なる順序で印刷されても、同等に比較される場合があります。

let first: Set = ["A", "B", "C", "D", "E", "F"]
print(first)  // ["B", "E", "C", "F", "D", "A"]
let second: Set = ["A", "B", "C", "D", "E", "F"]
print(second)  // ["A", "D", "E", "F", "C", "B"]
print(first == second)  // true

キーポイント:

• Setメンバーが同じかどうかだけが問題です。
• print(first)そしてprint(second)順序は異なる場合があります。
• first == secondまだtrue。 ●軽量化のみを必要とするシーンに最適なモデルです。

（20:26）OrderedSet広告掲載オーダーを保存します。等価比較に順次参加します。メンバーコレクションのみに関心がある場合は、次を使用できますunorderedビュー。

import Collections

let first: OrderedSet = ["A", "B", "C", "D", "E", "F"]
print(first)         // ["A", "B", "C", "D", "E", "F"]

let second: OrderedSet = ["F", "E", "D", "C", "B", "A"]

print(first == second)                      // false
print(first.unordered == second.unordered)  // true

キーポイント:

• OrderedSet配列リテラルを使用して作成できます。
• print(first)リテラル内の順序を保持します。
• first == secondメンバーを比較して順序付けします。
• unorderedビューは順序を無視し、メンバーのみを比較します。

（21:04）OrderedSet整数の添字付け、配列のような並べ替えとシャッフルをサポートし、セットのような重複要素を回避します。

import Collections

var items: OrderedSet = ["E", "D", "C", "B", "A"]
items[3]  // "B"
items.append("F")         // (inserted: true, index: 5)
items.insert("B", at: 1)  // (inserted: false, index: 3)
items.remove("E")
items.sort()
items.shuffle()

キーポイント:

• items[3]位置によって要素にアクセスします。
• append("F")新しい要素を挿入し、それが挿入されたかどうかと要素のインデックスを返します。
• insert("B", at: 1)発見する"B"はすでに存在するため、既存の添字が返されます。
• remove("E")要素ごとに削除します。
• sort()そしてshuffle()並べ替え操作を実行します。

OrderedDictionary: キーによる検索。キーと値のペアの順序も保持します。

（26:46）OrderedDictionary辞書の順序付けられたバージョンです。キーを使用して値をチェックし、キーと値のペアの特定の順序を維持します。デフォルトはキーの挿入順序です。

import Collections

var dict: OrderedDictionary = [2: "two", 1: "one", 0: "zero"]

print(dict[1])  // Optional("one")
print(dict)     // [2: "two", 1: "one", 0: "zero"]

dict[3] = "three"
dict[1] = nil
print(dict)     // [2: "two", 0: "zero", 3: "three"]

キーポイント:

• OrderedDictionary辞書リテラルを使用して作成できます。
• dict[1]キーごとに値を読み取ります。
• print(dict)決定されたキーと値のペアのシーケンスを表示します。
• dict[3] = "three"新しいキーの要素を追加します。
• dict[1] = nil既存のキーを削除します。

（27:38）OrderedDictionary添え字は常にキーの添え字を表します。場所ごとにキーと値のペアにアクセスするには、次のようにする必要があります。elementsビュー。

import Collections

var dict: OrderedDictionary = [2: "two", 0: "zero", 3: "three"]

print(dict[0])           // Optional("zero")

print(dict.elements[0])  // (key: 2, value: "two")

キーポイント:

• dict[0]キーの検索0価値。
• この操作は戻りますOptional("zero")。
• dict.elementsランダムアクセスコレクションビューです。
• dict.elements[0]位置 0 のキーと値のペアを返します。
• スピーチノート、OrderedDictionaryそれ自体は以下にのみ準拠しますSequence、集団的な行動が必要な場合に使用されますelements。

重要ポイント

1. やるべきこと: チャット アプリに「時間間隔による日付区切りバーを挿入」を追加します。

• 実行する価値がある理由: 迅速なアルゴリズムchunkedそしてjoined「隣接する要素でグループ化し、グループ間に区切り文字を挿入する」というプロセスは説明されました。
• 開始方法: メッセージ アイテムを公開しますdate、使用.chunked { $1.date.timeIntervalSince($0.date) < 60 * 60 }グループ化して再利用する.joined { DateItem(date: $1.first!.date) }タイムスタンプを挿入します。

2. やるべきこと: 最近見た写真バーを実装して、最後の 6 枚の写真のみを表示します。

• 実行する価値がある理由: 標準ライブラリのアルゴリズム チェーンは、手書きのリバース ループを置き換えることができます。.lazy中間配列を削減できます。
• 開始方法: トランスクリプトから.lazy.compactMap { $0 as? PhotoItem }.suffix(6).reversed()、そして最後に使用しますArray(...)結果を保存します。

3. 対処方法: ダウンローダーまたはタスク システムを両端タスク キューに変更します。

• 実行する価値がある理由:Deque先頭と末尾の挿入と削除に適しています。挿入を開始する場合、既存の要素を移動する必要はありません。
• 開始方法: を使用しますDeque<Task>保留中のタスクを保存します。通常のタスクappend、優先度の高いタスクprepend、タスクを消費するときremoveFirst()。

4. やるべきこと: ドラッグ アンド ドロップで並べ替え可能なタグ マネージャーを作成します。

• 実行する価値がある理由:OrderedSet独自性とユーザー指定の順序を同時に表現するため、「ラベルの繰り返しはできないが順序は保存する必要がある」といったUIに適しています。
• 開始方法: を使用しますOrderedSet<Tag>データソースとして;新しいタグを追加するためappend;ドラッグ後に並べ替えまたは移動ロジックを呼び出します。メンバーのみを比較する場合に使用されます.unordered。

5. やるべきこと: 順次安定した構成エディターを構築します。

• 実行する価値がある理由:OrderedDictionaryキーで値を素早く確認でき、設定項目を挿入順に表示できます。
• 開始方法: を使用しますOrderedDictionary<String, SettingValue>構成を保存します。で値を読み取りますdict[key];リスト表示の場合dict.elements。

関連セッション

• Swift の新機能 - このセッションの言語背景を理解するのに役立つ、Swift 5.5、同時実行モデル、および Swift オープン ソース パッケージ エコシステムを紹介します。
• Swift 同時実行: サンプル アプリを更新する — 新しい Swift 言語機能を実際のアプリ コードに適用する方法を示します。
• Swift の ARC: 基本とその先 — アルゴリズム チェーンやコレクション パフォーマンスの最適化と同じタイプの基本機能に属する Swift のメモリ管理動作について説明します。
• 結果ビルダーを使用して Swift で DSL を作成する - Swift の構文抽象化機能について説明しており、Swift の表現力の学習の拡張として適しています。