Ha what a simple but great implementation! Seems obvious in retrospect. > On 22 May 2016, at 7:53 AM, Dave Abrahams via swift-evolution > <[email protected]> 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 > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
