>> 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
}
`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.
> 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.
--
Brent Royal-Gordon
Architechies
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
