CODEWITHSUNDEEP
arraysswift
matt
matt

Reputation: 535860

Is Swift array reversed()[n] efficient or not?

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?

Upvotes: 28

Views: 2619

Answers (2)

CrystDragon
CrystDragon

Reputation: 131

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

Upvotes: 2

Itai Ferber
Itai Ferber

Reputation: 29918

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:

  1. BidirectionalCollection.reversed(), which returns a ReversedCollection, and
  2. Sequence.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.

Upvotes: 36

Related Questions