In WWDC 2018 Swift Generics (the online video doesn't play for me, must download the mp4). At 21:07, the binary search insertion example @Douglas_Gregor uses RandomAccessCollection, but BidirectionalCollection also works and is more general. Is there some reason for this? For my own binary search I use BidirectionalCollection, want to be sure I'm not making a mistake and should use RandomAccessCollection instead.
// BidirectionalCollection is more general and works just as well
// is there good reason this example used RandomAccessCollection?
// vvvvvvvvvvvvvvvvvvvvvv
extension BidirectionalCollection/*RandomAccessCollection*/ where Element: Comparable {
func sortedInsertionPointRecursive(of value: Element) -> Index {
if isEmpty { return startIndex }
let middle = index(startIndex, offsetBy: count / 2)
if value < self[middle] {
return self[..<middle].sortedInsertionPoint(of: value)
} else {
return self[index(after: middle)...].sortedInsertionPoint(of: value)
}
}
// non-recursive version
func sortedInsertionPoint(of value: Element) -> Index {
// cannot do type inference: error: Expected type
var slice: SubSequence = self[...]
while !slice.isEmpty {
let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
if value < slice[middle] {
slice = slice[..<middle]
} else {
slice = slice[index(after: middle)...]
}
}
return slice.startIndex
}
}
The key is right here. To ensure that binary search performs on logarithmic time, you need be able to jump to the middle entry in O(1). That performance is guaranteed by RandomAccessCollection, but not BidirectionalCollection.
Now, if you use BidirectionalCollection, it can only guarantee up to O(k). If you do the math, the entire binary search will take O(n) time. Not terrible, but you might as well just look at each element one by one.
I thought even though the extension is on BidirectionalCollection, if you call it on a RandomAccessCollection, then it will call the index(:offsetBy:) on that, which is O(1).
That is correct. Still, it doesn't change the fact that this isn't a great tool for a general BidirectionalCollection to have. I mean, I won't stop you, but as said, a simple for-loop will probably work just as well.
It's not O(0), not guaranteed to be, anyway.
You can try to think about how it'd work with String, which has non-uniform element size (and is bidi).
Also, treaded carefully, even Collection would provide the correct result.
I view these functions as algorithm operating on any collection, its performance characteristic is determined by the implementation of the actual Collection and it's up to the caller to decide.
I just noticed this also. He uses SubSequence and doesn't use index(before:), seem even better to be able to used on any Collection.
I have my quarrels with the whole Sequence-hierarchy, but imho (this applies to the whole of this post ;-) BidirectionalCollection is especially odd: I couldn't tell a single conforming type that is not also RandomAccessCollection — and the name shouts "DoubleLinkedList" at me (which is a very basic and prominent concept, but does not fit well into the system of protocols at all).
So the benefit of BidirectionalCollection is just theory, whereas in practice it might bite you because of some default implementation (but that's less than a theory, and I didn't check if offset operations are slower when you use a RandomAccessCollection as BidirectionalCollection).
Therefor, I'd ignore BidirectionalCollection as well.
of course — String! But is that actually the only one?
However, with all its unicode-quirks, String is somewhat special anyways — and afaics, index(before:) should be quite complex as well.
Surprisingly, Slice is also marked bidirectional, even when the base collection isn't… so BidirectionalCollection really does not seem to offer strong guarantees.
of course —