Missed optimization in ReversedCollection?

Using Swift
1

I wrote up an answer to this StackOverflow question which involved summing the integers along the diagonal of a matrix. Here's the relevant part:

// The sum of elements along the diagonal from top-right to bottom-left
func diagonal2Sum(_ input: [[Int]]) -> Int {
    input.indices
        .map { input[$0].reversed()[$0] } // Use the existing `reversed()` property to do the index math for us.
        .reduce(0, +)
}

The goal was to circumvent the need to write input[$0][input.count - $0 - 1] (which was the root cause of OP's question, they forgot the - 1 term), by instead having reversed() do the work for us.

I suggested this under the misapprehension that subscript the ReversedCollection returned by Array.reversed() would just do some cheap index arithmetic in constant time. Surprise, I was dead wrong!

@mattneub opened a new question on that topic, and @itaiferber explained that that this is calling another overload of reversed(), Sequence.reversed(), which returns an array (with the full linear-time reversing that entails).

Is there something that could be done to standard library to allow it to identify collections whose indices have the property that the "nth last index is just count - n - 1", and to allow a constant time reversed view into the underlying collection?

1 Like
2

FYI your map is producing a whole new array.

You should probably either add .lazy before the map, or else eliminate the map entirely and just use reduce.

Adapting your accepted answer, the latter would look something like:

// The sum of elements along the diagonal from top-right to bottom-left
func diagonal2Sum(_ input: [[Int]]) -> Int {
  let z = zip(input.indices, input.indices.reversed())
  return z.reduce(0){ $0 + input[$1.0][$1.1] }
}

• • •

That would probably require a new protocol which refines RandomAccessCollection and places additional constraints on the indices.

4

You asked for a "constant time reversed view into the collection", but ReversedCollection already gives you that: it just uses a different constraint. Concretely, ReversedCollection conforms to RandomAccessCollection (a constant-time indexing view) whenever the base collection does too: see the definition.

What you appear to want is an overload for ReversedCollection where it accepts the indices of the base collection, but happens to iterate them backwards. I think this would have a bunch of nasty sharp edges, most of which appear when you call reversed() on a collection with Index == Int. This would produce a Collection that has integer indices but indexes them backwards, meaning index + 1 is actually the previous element instead of the next one. I think that would be extremely gross, and likely to cause confusion. For opaque indices this would be workable, but that ship has largely sailed, and having a different index type in the case of the two conformances would not be practical anyway.

1 Like
5

Here's an ad-hoc solution for you.

By overloading subscript yourself, we can guide the compiler to choose our implementation.

extension ReversedCollection where Base: RandomAccessCollection {
  subscript(_ offset: Int) -> Element {
    let index = index(startIndex, offsetBy: offset)
    return self[index]
  }
}