[swift-evolution] [Discussion] Binary search, lower bound, upper bound, equal range

[plx]

> On Feb 16, 2016, at 11:58 AM, Pyry Jahkola via swift-evolution <swift-evolution at swift.org> wrote:
> 
>> On 16 Feb 2016, at 17:49, Jeff Hajewski <jeff.hajewski at gmail.com <mailto:jeff.hajewski at gmail.com>> wrote:
>> 
>> I wonder if we can loosen the restriction of conforming to RandomAccessIndexType.
> 
> Yay, it turned out simpler than I thought!
> 
> I added a performance test to make sure there's no regression on RandomAccessIndexType's performance, then simply downgraded the RandomAccessIndexType requirement to ForwardIndexType (and used != instead of < in a few places). The updated code <https://github.com/knomi/Allsorts/commit/52e3d7abee2d01d90ecadea24e00c9067a64a327> is in GitHub.
> 
> That appears to work because of protocol inheritance magic in the standard library. So, even though my search algorithm only knows about ForwardIndexType, whenever Index happens to implement O(1) versions of advancedBy(_:) and distanceTo(_:), then those get used instead of the O(N) default implementations (Index.swift <https://github.com/apple/swift/blob/de253d9b6f21498704f96aac712cf1b02e612255/stdlib/public/core/Index.swift#L243-L262> on the Swift repository). Cool!
> 
> There might still be place for improvement, since the internal use of midIndex still passes across the same index ranges several times during the search on ForwardIndexType. If I did my math right, the current implementation makes something like 3N index increments on ForwardIndexTypes, while probably at least 2N can be achieved without much memory use.

I was going to suggest earlier that the algorithms should perhaps switch to an internal representation of ~ `(index: Index, length: Index.Distance)` (instead of `Range<Index>`), which is an unnecessary change for `RandomAccessIndexType` but for a `ForwardIndexType` would eliminate the need to call `distanceTo` more than once.

The public API could of course stick with Range<Index>, the alternative representation would only be a private implementation detail.

I have some other thoughts but they’re still in progress.

> 
>> I think maybe the Ordering enum should be broken out into a separate proposal since it's not currently part of the standard lib. That being said, it does make for a clean implementation.
> 
> You're absolutely right. I should also paint the bikeshed of naming its cases (.LT, .EQ, and .GT) less obscurely before officially proposing it to swift-evolution. Maybe either  .ascending, .equivalent, and .descending, or simply .less, .equal, and .greater. And I expect there to be resistance against adding yet another comparison operator, even if there's precedent on the use of something like "a <=> b" in several other languages.
> 
> — Pyry Jahkola
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160216/78e471ca/attachment.html>