SequenceType Binary Search Implementation


(Lorenzo Racca) #1

Hi all,

I’m kinda new to this, so here’s my idea.
The other day I was building an app and had to search through a pretty big array (some 100M entries), and noticed the library function “array.contains” slowed everything down a lot. So i searched on GitHub the code and found out that "SequenceType.contains” uses Linear Search. I know that Binary Search works way better with sorted arrays (which was my situation) so here it is, why not add it to the std lib?
I noticed it because I moved from C# where such a function is present. And I believe there is one in Java too.

I was working and I already figured out an algorithm that could really be just pasted into SequenceType.swift and make it easy for everyone. I even started benchmarking it and really, it would make a big difference. This is my code as of now:

extension CollectionType where Generator.Element : Comparable {
    /// Returns `true` if `element` is in `self`.
    /// Collection must be sorted.
    @warn_unused_result
    public func binarySearch(element: Generator.Element) -> Bool {
        if let result = _customContainsEquatableElement(element) {
            return result
        }
        
        var left = startIndex
        var right = endIndex
        
        while (left != right) {
            let mid = left.advancedBy(left.distanceTo(right) / 2)
            let value = self[mid]

            if (value == element) {
                return true
            }
            if ( value < element) {
                left = mid.advancedBy(1)
            }
            if (value > element) {
                right = mid
            }
        }
        return false
    }
}

Now I don’t know whether this would be accepted, useful or just even right. I don’t have the permission to pull commits to the rep, so I don’t even really know how to make it an official proposal.

Any thoughts on this?

Lorenzo Racca
+39 345 9294756
lorenzo.racca@live.it


(Dmitri Gribenko) #2

Hi Lorenzo,

The absence of binary searches is a known blank spot in the library,
and I'm glad that you are interested in fixing this.

We have a bug that tracks this issue: https://bugs.swift.org/browse/SR-368

Since this is an API change, we need to follow the Swift evolution
process [1]. I would appreciate if you could lead the conversation!
The way to word the initial email would be to present the proposed API
(not the implementation), and doc comments that explain the semantics.

Some specific advice for designing this API:

- Please familiarize yourself with C++ binary_search, lower_bound,
upper_bound, and equal_range APIs. I'm not saying that these are the
best APIs for Swift, but these specific formulations have proven to be
useful in C++.

- Make sure you have overloads for 'Generator.Element : Comparable'
case as well as unconstrained overloads, where the comparison
predicate is supplied as a function parameter.

- Think about returning an boolean flag, returning the element, and
returning the element's index. Which is the most primitive one that
others can be built on top with? Which ones do we need to make
commonly-written code read well without extra complexity?

[1] https://github.com/apple/swift-evolution/blob/master/process.md

Thank you for tackling this problem!

Dmitri

···

On Fri, Mar 11, 2016 at 8:11 AM, Lorenzo Racca via swift-dev <swift-dev@swift.org> wrote:

Now I don’t know whether this would be accepted, useful or just even right.
I don’t have the permission to pull commits to the rep, so I don’t even
really know how to make it an official proposal.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/