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

[Jeff Hajewski]

Dave,

Thanks a lot for the feedback - it is greatly appreciated. With respect to your comment about the unary partitioning predicate, I really like that idea and hadn’t thought of the problem like that. Excellent suggestion!

Thanks
Jeff

> On Feb 15, 2016, at 4:34 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> on Mon Feb 15 2016, Jeff Hajewski <swift-evolution at swift.org> wrote:
> 
>> Hello,
>> 
>> I am working on SR-368 <https://bugs.swift.org/browse/SR-368> and am hoping to get some feedback from the community.
>> 
>> Description
>> Implement analogs to C++’s binary_search, lower_bound, upper_bound, and equal_range algorithms.
>> 
>> Initial Proposal
>> I propose adding four methods for generic Array and adding four
>> methods for Arrays that conform to Comparable:
>> 
>> Array
>> @warn_unused_result
>> func lowerBound(value: Array.Element, @noescape isOrderedBefore: (lhs:
>> Array.Element, rhs: Array.Element) -> Bool) -> Int?
>> 
>> @warn_unused_result
>> func upperBound(value: Array.Element, @noescape isOrderedBefore: (lhs:
>> Array.Element, rhs: Array.Element) -> Bool) -> Int?
>> 
>> @warn_unused_result
>> func binarySearch(value: Array.Element, @noescape
>> isOrderedBefore:(lhs: Array.Element, rhs: Array.Element) -> Bool) ->
>> Bool
>> 
>> @warn_unused_result
>> func equalRange(value: Array.Element, @noescape isOrderedBefore: (lhs:
>> Array.Element, rhs: Array.Element) -> Bool) -> Range<Int>?
>> 
>> Array: Comparable
>> @warn_unused_result
>> func lowerBound(value: Array.Element) -> Int?
>> 
>> @warn_unused_result
>> func upperBound(value: Array.Element) -> Int?
>> 
>> @warn_unused_result
>> func binarySearch(value: Array.Element) -> Bool
>> 
>> @warn_unused_result
>> func equalRange(value: Array.Element) -> Range<Int>?
>> 
>> Discussion
>> The main issue I’d like to discuss is how do we want to add these to Swift? My thoughts are as follows:
>> 
>> These should be as generic as possible. I initially started at the
>> CollectionType level but it seemed that the problem was ultimately
>> reduced to an Array (through the use of various protocols, etc.). 
> 
> These should be defined on CollectionType Note that you don't need
> random access to get an advantage from binary search if the comparison
> is sufficiently expensive.
> 
>> For example, suppose we implemented these methods as an extension to
>> CollectionType, if we were to try and call binarySearch on a set, we
>> would first need to sort the set, which would return an array, and
>> then we would call binarySearch on that array. 
> 
> It should work on any arbitrary collection.  The collections you know
> are not the only ones that matter.  For examples, consider binary
> searching the result of applying a lazy map or filter to some sorted
> array.
> 
>> Similarly, it seems at the SequenceType level the problem ultimately
>> reduces to using Array.
> 
> Sequences don't have indices; you can't binary search them.
> 
>> Does it make sense to handle these as public functions? I tend to
>> think not as it seems less idiomatic.  I suggest eight implementations
>> similar to how sort() is handled. If the calling array’s elements
>> conform to Comparable, then no isOrderedBefore closure is required
>> since we can use “<“, otherwise the user should supply a closure to
>> allow the algorithm determine how the array elements are ordered.
> 
> The general form takes a closure that partitions the collection; see
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html and
> http://wg21.cmeerw.net/lwg/issue270
> 
> I would suggest avoiding the API choice that requires both a comparison
> closure *and* an element against which to compare, as a unary
> partitioning predicate is much simpler.
> 
>> Similar to the C++ implementations, I avoid recursion and favor
>> while-loops.
> 
> 
> Have an implementation is important as proof-of-concept and for
> performance testing, but I don't consider the details important at this
> stage.
> 
>> These methods should be preconditioned on the calling
>> array be partitioned with respect to the passed value. 
>> As far as I’m aware, there is no “isPartitioned(value:)” method
>> currently available. 
>> 
>> Should we add this as well? We could use this functionality and not
>> add a isPartitioned method but if we are adding this functionality is
>> there a good reason not to give the public access?  
> 
> Seems like a separable proposal.
> 
>> The alternative is to not set a precondition and document that the
>> results may not be valid if the calling array is not partitioned with
>> respect to value. 
> 
> That *is* a precondition.  Not all preconditions can or should be
> verfied at runtime.  We would never make the caller pay to actually
> verify at runtime that the collection is partitioned w.r.t. the closure;
> that would make the whole operation O(N) and effectively discard any
> benefit of binary-searching.
> 
>> I favor the preconditioning approach.
>> 
>> Any and all feedback is greatly appreciated!
> 
> 
> HTH,
> Dave
> 
> 
> -- 
> -Dave
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution