Swift Digest
SE-0074 | Swift Evolution↗

Implementation of Binary Search functions

Proposal
SE-0074↗
Authors
Lorenzo Racca, Jeff Hajewski, Nate Cook
Review Manager
Chris Lattner
Status
Rejected

01 何が問題だったのか

配列のように順序を持つコレクションの中から、ある値が含まれているか、含まれているなら何番目にあるかを知りたい場面はよくあります。Swift 標準ライブラリにはそのための API として Sequence.contains(_:) や Collection.index(of:) がありますが、これらはいずれも先頭から順に要素を比較していく線形探索で、コレクションが大きくなるほど O(n) のコストがかかります。10 万件を超えるような大きな配列で頻繁に検索する場合、この O(n) は無視できないコストになります。

ソート済みであることを活かせない

要素があらかじめソートされている場合、二分探索を使えば探索コストを O(log n) まで下げられます。しかし Swift 標準ライブラリには、「このコレクションはソート済みである」という前提で動作する検索 API がそもそも用意されていません。そのため、利用者は次のいずれかを選ばざるを得ませんでした。

  • ソート済みであることが分かっていても、contains(_:) や index(of:) による O(n) の線形探索を使う
  • 二分探索のロジックを自前で書く（インデックス計算や境界条件で間違えやすい）
  • サードパーティのライブラリに依存する

また、同じ値が複数含まれているソート済みコレクションで、「その値に等しい要素の範囲」を取り出したい場合や、ある述語に対する「パーティション境界」を求めたい場合も、既存 API では簡潔に書く手段がありませんでした。

既存の partition() は用途が限定的

一方で、当時の標準ライブラリには partition() / partition(isOrderedBefore:) というメソッドが存在していました。これはコレクションを「先頭要素」を基準に並べ替えるもので、主に標準ライブラリ内部のソート実装から利用されるためのものでした。利用者側が「任意の述語に従って要素を前後に分ける」という一般的なパーティション操作をしたい場合には使い勝手が悪く、用途が限定的でした。

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

この提案は Rejected（却下） となりました。二分探索を標準ライブラリに加えるという方向性自体はコアチームからも前向きに評価されましたが、提案された API が一度に導入する要素が多く複雑すぎるという判断で、この提案はそのままの形では採用されませんでした。現在の Swift 標準ライブラリにも、この提案そのものに対応するメソッドは入っていません。

提案されていた内容（却下されたもの）

提案は、Collection に対して二分探索に基づく 3 つのメソッドと、任意の述語で要素を前後に分けるパーティション用メソッドを追加するものでした。例として次のような配列を考えます。

let a = [10, 20, 30, 30, 30, 40, 60]

partitionedIndex(where:)

単項述語を受け取り、述語を満たさない最初の要素のインデックスを返します。コレクションはすでにその述語でパーティション化されている必要があります。C++ STL の partition_point に相当します。

a.partitionedIndex(where: { $0 < 20 })      // 1

// 二項述語からは lower / upper bound を作れる
a.partitionedIndex(where: { $0 < 30 })      // 2（lower bound）
a.partitionedIndex(where: { !(30 < $0) })   // 5（upper bound）

sortedIndex(of:)

ソート済みコレクションから、指定した値のインデックスを返します。見つからなければ nil を返します。C++ の binary_search に近いものの、見つかった位置を返すためより使いやすい設計です。比較関数を渡す版もあり、降順にソートされたコレクションにも使えます。

a.sortedIndex(of: 30)   // 2
a.sortedIndex(of: 60)   // 6
a.sortedIndex(of: 100)  // nil

let r = [60, 40, 30, 30, 30, 20, 10]
r.sortedIndex(of: 60, isOrderedBefore: >)  // 0

sortedRange(of:)

同じ値が連続して並んでいるソート済みコレクションから、その値に等しい要素の範囲を返します。見つからなければ、挿入位置を startIndex とする空の範囲を返します。C++ の equal_range に相当します。

a.sortedRange(of: 30)   // 2..<5
a.sortedRange(of: 50)   // 6..<6（空の範囲。ここに挿入すればソート済みを保てる）

partition(where:)

任意の単項述語に従ってコレクションを並べ替える mutating メソッドです。述語を満たす要素群と満たさない要素群の境界となるインデックスを返します。

var n = [30, 40, 20, 30, 30, 60, 10]
let p = n.partition(where: { $0 < 30 })
// n == [30, 20, 30, 30, 10, 40, 60]
// p == 5

境界の前（n.prefix(upTo: p)）は述語が true、境界以降（n.suffix(from: p)）は false となります。既存の partition() / partition(isOrderedBefore:) は、この partition(where:) で表現できるうえに用途も広いため、置き換えとともに削除する計画でした。

カスタマイズポイント

将来ユーザー定義の「ソート済みコレクション型」が contains(_:) や index(of:) を O(log n) で提供できるよう、Sequence / Collection に _customContainsComparableElement(_:) と _customIndexOfComparableElement(_:) というアンダースコア付きのカスタマイズポイントを追加する計画も含まれていました。デフォルト実装は nil を返し、独自の実装を提供した型だけが効率的な検索に置き換わる仕組みです。

却下の理由

レビュー結果では、二分探索を加えたいという動機には賛同しつつも、提案されている API が一度に導入するものが多く、標準ライブラリに載せるには複雑すぎるという判断が示されました。具体的には、3 種類の検索メソッド、パーティション API、そしてカスタマイズポイントまで一度に追加する設計になっており、それぞれの必要性や命名をもう少し切り分けて議論すべきという方向性です。

現在の Swift での書き方

現時点の標準ライブラリには、ソート済みであることを前提とする検索 API は入っていません。大きなソート済みコレクションを頻繁に検索する必要がある場合は、用途に合った二分探索を自前で書くか、Swift Collections などのサードパーティライブラリで提供されるソート済みコレクション型を利用するのが現実的です。一方で、パーティション操作については後に SE-0120 で partition(by:) として整理された形で標準ライブラリに入り、任意の述語で要素を前後に分ける機能自体は利用できるようになっています。