When you call reversed()
on an array in Swift, you get a ReverseCollection which merely wraps the original array with reversed access. Thus this is extremely efficient:
let arr = [1,2,3,4] for i in arr.reversed() { print(i) }
Nothing actually got reversed except the access; the time complexity of reversed
here is O(1). Cool!
But when I index into reversed()
by an integer and check Quick Help, it appears I've lost all that efficiency; I'm shown the Sequence reversed()
which generates a new array:
let arr = [1,2,3,4] let i = arr.reversed()[1] // ???? this is a different `reversed()`!
And this seems to be true, because a reversed()
array does not, itself, support indexing by number:
let arr = [1,2,3,4] let rev = arr.reversed() let i = rev[1] // compile error!
So my question is: is it really true that indexing by number into a reversed()
array, as in my second example, loses the efficiency of the ReverseCollection index reversal?
Yes, indexing by Int
is causing you to lose your O(1)
access into the reversed array. Quite the gotcha!
As you note, reversed()
here is an overloaded method; on Array
specifically, you have two definitions to choose from:
BidirectionalCollection.reversed()
, which returns a ReversedCollection
, andSequence.reversed()
, which turns any sequence into a reversed [Element]
The overloading here is most confusing for Array
itself, because it's the only Sequence
type such that type(of: x) == type(of: x.reversed())
.
The Swift type checker prefers more specific overloads over less-specific ones, so in general, the compiler will use the BidirectionalCollection
overload instead of the Sequence
one where possible. The rub: BidirectionalCollection
has an opaque index type, and cannot be indexed using an Int
; when you do index into the collection with an Int
, the compiler is instead forced to choose the Sequence
overload over the BidirectionalCollection
one. This is also why your second code sample fails to compile: Swift code inference does not take into account surrounding context on other lines; on its own, rev
is preferred to be a ReversedCollection<Array<Int>>
, so attempting to index into it with an Int
fails.
You can see this a little more clearly with the following:
func collType1<T: Collection>(_: T) { print(T.self) // ReversedCollection<Array<Int>> print(T.Index.self) // Index } func collType2<T: Collection>(_: T) where T.Index == Int { print(T.self) // Array<Int> print(T.Index.self) // Int } let x: [Int] = [1, 2, 3] collType1(x.reversed()) collType2(x.reversed())
Lest you wonder whether the compiler can optimize around this when the fact of Int
-based indexing appears to not have any other side effects, at the time of writing, the answer appears to be "no". The Godbolt output is a bit too long to reproduce here, but at the moment, comparing
func foo1(_ array: [Int]) { if array.reversed()[100] > 42 { print("Wow!") } }
with
func foo2(_ array: [Int]) { if array.reversed().dropFirst(100).first! > 42 { print("Wow!") } }
with optimizations enabled shows foo2
performing direct array access
cmp qword ptr [rdi + 8*rax + 24], 43
having optimized away the ReversedCollection
wrapper entirely, while foo1
goes through significantly more indirection.
Ferber explained the reason very well.
Here's an ad-hoc solution (which may not be preferred by everyone, because we are extending types from the standard library):
// RandomAccessCollection ensures fast index creation extension ReversedCollection where Base: RandomAccessCollection { subscript(_ offset: Int) -> Element { let index = index(startIndex, offsetBy: offset) return self[index] } } [1, 2, 3].reversed()[0] // 3
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With