SE-0120 | Swift Evolution↗

Revise `partition` Method Signature

Proposal: SE-0120↗
Authors: Lorenzo Racca, Jeff Hajewski, Nate Cook
Review Manager: Chris Lattner
Status: Implemented (Swift 3.0)

01 何が問題だったのか

標準ライブラリの MutableCollection には、以前から partition という整列用のメソッドが存在していました。しかしこの partition は「ソートの内部実装」に寄った設計になっており、コレクションを汎用的に分割するために使うには不便でした。

当時の `partition` は「先頭要素を基準にした2分割」しかできなかった

当時の partition は、コレクションの先頭要素を暗黙的にピボットとして使い、渡された2引数の述語で比較して要素を並べ替える、というものでした。イメージとしては、クイックソートの1ステップをそのままメソッドにしたような形です。

var numbers = [30, 40, 20, 30, 30, 60, 10]
// 当時の partition: 先頭要素 30 をピボットにして、
//                  述語（<）に従って要素を並べ替える
let p = numbers.partition(isOrderedBefore: <)

この設計には、利用者から見て次のような使いにくさがありました。

ピボットに使う値を外から自由に選べない。常に「先頭要素」に固定される。
「条件に合うもの／合わないものに分けたい」という、もっとも素直なユースケースに直接対応していない。たとえば「30 より大きい要素を後ろに寄せたい」だけでも、< のような2引数比較を組み立てて、しかもコレクションの先頭が都合のよい値になっているかを意識する必要がありました。
空のコレクションに対する挙動や、先頭要素が特殊な値だった場合のふるまいを考えるのが煩雑でした。

ソートの部品としてはよいが、分割アルゴリズムとしては汎用性が低い

そもそも partition という名前のアルゴリズムは、C++ の std::partition のように、任意の条件 に従ってコレクションを2グループに並べ替えるものとして広く知られています。標準ライブラリの partition はソートの内部部品としては機能していた一方で、この一般的な意味での「条件による分割」として使おうとすると API が合わず、利用例もほとんど見当たらないという状況でした。

同時期に議論されていた二分探索（SE-0074）のレビューでも「partition のシグネチャを見直したほうがよい」という指摘が標準ライブラリチームから挙がっており、標準ライブラリ API の安定化に向けて整理すべき項目の一つとして残っていました。

02 どのように解決されるのか

既存の2種類の partition メソッドを廃止し、単項の述語 を1つ受け取る新しい partition(by:) に置き換えることで、汎用的な分割アルゴリズムとして使えるようにします。

新しい `partition(by:)` のふるまい

partition(by:) は、渡された述語に従ってコレクションの要素を並べ替えます。結果として、あるインデックス p（ピボット）を境に、

p より前：述語が false を返す要素
p 以降：述語が true を返す要素

という並びになります。戻り値はこのピボット p です。述語に合う要素が1つも無ければ、戻り値は endIndex になります。

var numbers = [30, 40, 20, 30, 30, 60, 10]
let p = numbers.partition(by: { $0 > 30 })
// p == 5
// numbers == [30, 10, 20, 30, 30, 60, 40]

let first = numbers.prefix(upTo: p)
// first == [30, 10, 20, 30, 30]  // 30 より大きくない要素
let second = numbers.suffix(from: p)
// second == [60, 40]              // 30 より大きい要素

各パーティション内部の順序は保たれません（安定ではありません）。計算量は O(n) で、全要素を1回走査するコストで分割できます。

ラベルが `by` である理由

引数ラベルには where ではなく by が採用されています。where は index(where:) のように「既に存在する要素の位置を探す」というニュアンスで使われているラベルです。一方 partition(by:) は、述語に合わせて コレクション自体を並べ替える 操作なので、sort(by:) と同じ系統として by が選ばれました。

`MutableCollection` の要件として追加

partition(by:) は MutableCollection の要件として追加され、前進のみのミュータブルコレクションと双方向ミュータブルコレクションそれぞれに、デフォルト実装が与えられます。どちらでも分割自体は可能ですが、双方向コレクション向けの実装のほうが代入回数を大幅に減らせるため、効率的です。

protocol MutableCollection {
    // 既存の要件に加えて、次の要件が追加される
    mutating func partition(
        by belongsInSecondPartition: (Iterator.Element) throws -> Bool
    ) rethrows -> Index
}

述語は throws に対応しており、rethrows によって呼び出し側に例外を伝播できます。

既存コードの書き換え

既存の partition()（先頭要素をピボットにする旧API）を使っていたコードは、次のように書き換えます。先頭要素を自分で取り出し、それを使う述語を組み立てて partition(by:) に渡す、という形です。

// 旧API
let p = c.partition()

// 新API
let p = c.first.flatMap({ first in
    c.partition(by: { $0 >= first })
}) ?? c.startIndex

旧 partition の実利用は GitHub 上でもほとんど見つからなかったため、実務上の影響は限定的と見込まれており、必要であればマイグレーションツールで機械的に書き換えることも想定されていました。

使いどころ

partition(by:) は、次のような「条件でグループ分けしたい」場面に素直に使えます。

var tasks = [
    (title: "レビュー", isDone: false),
    (title: "デプロイ", isDone: true),
    (title: "会議",     isDone: false),
    (title: "設計",     isDone: true),
]

// 未完了を前、完了を後ろに寄せる
let pivot = tasks.partition(by: { $0.isDone })
// tasks[..<pivot] が未完了、tasks[pivot...] が完了

ソートと比べて計算量が O(n) で済むため、順序そのものではなく「条件に合うかどうか」だけで分けたいケースでは、sort より partition(by:) のほうが軽量に目的を達成できます。

Revise partition Method Signature