[swift-evolution] (Draft) Add last(where:) and lastIndex(where:) methods

[Dave Abrahams]

on Sat May 21 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

>>> Similarly, we shouldn't provide operations which are going to
>>> repeatedly seek elements near the tail of the list unless we're using
>>> a type which can access that tail efficiently. `last` is one
>>> thing—it's only O(N). `lastIndex(of:)` is, I believe, O(n log n) in
>>> the case of an element that doesn't exist.
>> 
>> I can't imagine where your O(N log N) comes from in this case, but even
>> if it is the right complexity that wouldn't be a reason not to provide
>> the operation.
>
> I'm imagining an implementation something like this:
>
> 	func lastIndex(of value: Element) -> Index? {
> 		let count = self.count
>
> 		for endOffset in 0..<count {
> 			let offset = count - endOffset - 1
> 			let i = index(startIndex, offsetBy: offset)
>
> 			if self[i] == value {
> 				return i
> 			}
> 		}
>
> 		return nil
> 	}


Oh, no!

    extension Collection {
      func lastIndex(where predicate: (Element)->Bool) -> Index? {
        var result: Index? = nil
        for i in indices { 
          if predicate(self[i]) { result = i }
        }
        return result
      }
    }

    extension Collection where Element : Equatable {
      func lastIndex(of value: Element) -> Index? { 
        return lastIndex(where: { $0 == value })
      }
    }

> `index(_:offsetBy:)` is O(N) for a ForwardCollection, and `offset`
> gets smaller as you execute the loop, so I *believe* this ends up
> being O(N log N). I was never that good at big-O notation, though, so
> I could be wrong about that. What I can say is that it would be O(N^2)
> if not for the decreasing size of `offset`, so it's smaller than that.

What you wrote is still (N*(N - 1))/2 steps, i.e. O(N^2), in the worst
case, unless I'm missing something.

>> I learned last week there's an O(N log N) in-place
>> reverse() for ForwardCollections, and I think we ought to have it.  log
>> N is effectively a constant for most purposes.
>
> If you guys think it's okay, I'm not going to argue.

-- 
-Dave