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

[Patrick Smith]

Ha what a simple but great implementation! Seems obvious in retrospect.

> On 22 May 2016, at 7:53 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> 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
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution