このメソッドには問題がある
extension Array {
func reversedMap<T>(_ transform: (Element) -> T) -> [T] {
map(transform).reversed()
}
}
じょ
一見普通に見えるメソッドですが、何が問題なのでしょう
Array#reversed()
Arrayには要素の内容を逆順にするreversed()というメソッドがあります。
このメソッドはよくできていて、実際に要素が逆順になったArrayを生成せずにそのようにふるまうReversedCollection<Base>という型のインスタンスを返します。
このメソッドはArrayではなくBidirectionalCollectionプロトコル上にextensionとして実装されています。
func reversed() -> ReversedCollection<Self>
BidirectionalCollectionは要素を逆順に走査することができるコレクションですので、このreversed()を実装するのにちょうどよいプロトコルといえるでしょう。
Sequence#reversed()
感の良い方ならすでにお気づきだとは思いますが、初めに提示したreversedMapメソッドの戻り値はArrayとなっており、BidirectionalCollection#reversed()に適合していません。
ではこのArrayを戻すreversed()メソッドはどこから来たのでしょう。
それはSequenceプロトコル上にextensionとして実装されています。
func reversed() -> Array<Element>
Sequenceプロトコルは要素が順番に取り出せるということのみが規定されたプロトコルです。
PartialRangeFrom（5... のようなやつ）のように終端がないSequenceも実装可能です。
初めに提示したreversedMapメソッドはこちらのreversed()メソッドが使われているということです。
２つの相違
ではSequence#reversed()を使うことの何が問題なのでしょう。
ReversedCollection<Base>はBaseがBidirectionalCollectionであることを利用し、新たなCollectionを生成することなく逆順に要素を取り出すことができます。
ところがSequenceから逆順のArrayを生成するためには、すべての要素を取り出した上で逆順になったArrayを生成する必要があるのです。
計算量でいえばBidirectionalCollection#reversed()はO(1)で、Sequence#reversed()はO(N)です。
もちろんこの違いはとてつもなく大きいです。
じゃあどうすればいいの？
方法は２通りあります。
まずメソッドの順番を変える方法。
こちらの方がわかりやすいです。
extension Array {
func reversedMap<T>(_ transform: (Element) -> T) -> [T] {
reversed().map(transform)
}
}
reversed()メソッドを先に実行します。こうするとコンパイラはより適用範囲がより狭いBidirectionalCollection#reversed()を必ず選択します。
二つ目は戻り値の型を変える方法。
extension Array {
func reversedMap<T>(_ transform: (Element) -> T) -> ReversedCollection<Self> {
map(transform).reversed()
}
}
こうすることで、BidirectionalCollection#reversed()に固定されます。
ただし、ちょっと見た目がうるさいです。
まとめ？
手元でてきとーにテストしてみた結果、BidirectionalCollection#reversed()はSequence#reversed()より１割程度高速になります。
戻されたSequenceを使わないと意味がないのでテストは
measure {
s = array.reversedMap { i in i * 2 }.reduce(0, +)
}
で行いました。
すごくてきとーにやってますので興味がある方はお手元でお確かめください。