Swift Digest
Implement a rotate algorithm, equivalent to std::rotate() in C++
01 何が問題だったのか
配列のような線形なコレクションに対する「回転（rotation）」は、GUIや各種アルゴリズムの基礎部品として広く使われる操作です。ある区切り位置 middle を指定したとき、middle 以降の要素を先頭に、middle より前の要素を末尾側に付け替える、いわゆる左回転がこれにあたります。
var a = [10, 20, 30, 40, 50, 60, 70]
// shiftingToStart: 2 を指定すると、index 2 の要素が先頭に来るように回転させる
// a == [30, 40, 50, 60, 70, 10, 20]
標準ライブラリに回転操作がなかった
C++ の std::rotate に相当するこの操作は、当時のSwift標準ライブラリには存在しませんでした。自分で書こうとすると、コレクションが前方向のみ走査できるのか、双方向なのか、ランダムアクセスなのかに応じて最適なアルゴリズムが異なり、それぞれ別の実装を使い分けるのが定石です（前方向なら swap_ranges を繰り返す方式、双方向なら3回の reverse を組み合わせる方式、ランダムアクセスなら gcd を使ったサイクル分解方式）。これらを正しく実装するのは簡単ではなく、各プロジェクトが独自の回転ルーチンを抱え込むのは生産的ではありませんでした。
破壊的な reverse() も存在しなかった
双方向コレクションの回転は、実装上「前半・後半・全体の3回の in-place reverse」に帰着できます。ところが、Swift には当時、reversed() のような非破壊的に逆順ビューを返すメソッドはあっても、自身の要素を in-place で逆順にする破壊的な reverse() メソッドが用意されていませんでした。回転を効率的に実装するうえでも、また「配列の一部だけ逆順にしたい」といった日常的な場面でも、この不足は不便でした。
02 どのように解決されるのか
この提案は Returned for revision（差し戻し） となったのち改訂版が再提出されないまま、deferredとなっていたProposal群をまとめて整理する際に、最終的に差し戻し状態で終結しました。そのため、ここで提案されていた rotate(shiftingToStart:) / rotated(shiftingToStart:) や RotatedCollection といったAPIは、標準ライブラリには入っていません。一方で、提案の副産物として盛り込まれていた破壊的な reverse() は、後続の標準ライブラリの整備のなかで別途追加されています。
以下は、仮に採択されていた場合に導入される予定だった内容の要約です。
破壊的な rotate(shiftingToStart:)
MutableCollection に、指定した middle の要素が先頭に来るように要素を並べ替える破壊的メソッド rotate(shiftingToStart:) が追加される予定でした。戻り値は、回転前に先頭にあった要素の新しいインデックスです。この戻り値を二度目の rotate の middle に渡すと、元の並びに戻せます。
var a = [10, 20, 30, 40, 50, 60, 70]
let i = a.rotate(shiftingToStart: 2)
// a == [30, 40, 50, 60, 70, 10, 20]
// i == 5
a.rotate(shiftingToStart: i)
// a == [10, 20, 30, 40, 50, 60, 70]
このメソッドは MutableCollection のプロトコル要件として定義され、前方向・双方向・ランダムアクセスのそれぞれに対してデフォルト実装が用意されます。ジェネリックな文脈でも、コレクションの走査能力に応じた最適なアルゴリズムが選ばれる設計でした。計算量はいずれも O(n)です。
スライスに対する回転もそのまま使えるよう設計されていました。
var toMerge = [2, 4, 6, 8, 10, 3, 5, 7, 9]
let i = toMerge[2..<7].rotate(shiftingToStart: 5)
// toMerge == [2, 4, 3, 5, 6, 8, 10, 7, 9]
// i == 4
非破壊的な rotated(shiftingToStart:)
元のコレクションには手を加えず、回転済みの要素列を表すビューを返す非破壊形 rotated(shiftingToStart:) も提案されていました。ストレージを再確保しないため、計算量は O(1)です。
返り値の型は、元のコレクションの走査能力に応じて RotatedCollection / RotatedBidirectionalCollection / RotatedRandomAccessCollection のいずれかになり、元のインデックス種別が保たれます。これらのビューは、元コレクションの startIndex が回転後にどこへ移ったかを示す shiftedStartIndex プロパティを持ちます。
let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
let r = numbers.rotated(shiftingToStart: 3)
// Array(r) == [4, 5, 6, 7, 8, 9, 1, 2, 3]
// r[r.shiftedStartIndex] == 1
LazyCollectionProtocol にも同名のメソッドが追加され、遅延評価の形で回転を挟み込めるようになる予定でした。
let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
let r = numbers.lazy.rotated(shiftingToStart: 3)
// r.first! == 4
破壊的な reverse()
双方向コレクションの回転アルゴリズムが in-place reverse に依存することもあり、MutableCollection where Self: BidirectionalCollection に対して破壊的な reverse() メソッドを追加することも本提案に含まれていました。計算量は O(n)です。
var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
numbers.reverse()
// numbers == [9, 8, 7, 6, 5, 4, 3, 2, 1]
numbers[0..<5].reverse()
// numbers == [5, 6, 7, 8, 9, 4, 3, 2, 1]
本提案自体は差し戻されましたが、この破壊的 reverse() は、Swift 2 時代の reverse()（非破壊）を reversed() にリネームする一連の標準ライブラリ整備のなかで、別途標準ライブラリに取り込まれています。したがって、現行のSwiftでは Array などに対して reverse() を呼ぶと in-place で逆順化され、reversed() を呼ぶと逆順ビューが返る、という整った形になっています。
利用者として知っておくべきこと
- 現行のSwift標準ライブラリには、本提案で提案された
rotate(shiftingToStart:)やrotated(shiftingToStart:)は存在しません。回転操作が必要な場合は、自前で実装するか、Swift Algorithms パッケージが提供するrotate(toStartAt:)/rotated(toStartAt:)を利用するのが実用的な選択肢です。 - 本提案に含まれていた破壊的
reverse()に相当する機能は、別経路で標準ライブラリに取り込まれており、現在も使えます。