Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Dave Abrahams via swift-evolution]

on Mon Jan 30 2017, Nate Cook  wrote:

>> On Jan 30, 2017, at 2:47 AM, Alexey Komnin via swift-evolution 
>>  wrote:
>> 
>> Hello to everyone.
>> 
>> Let me put my two cents.
>
>> 
 I didn’t want the SortedArray to conform to MutableCollection or
 even RandomAccessCollection as I felt it was not needed just to
 support binary search and prevent re-sorting.
>>> 
>>> You are right not to support MutableCollection or
>>> RangeReplaceableCollection, as those would allow you to violate the
>>> “sorted” invariant.  However, it should conform to
>>> RandomAccessCollection; that's really easy to implement and would
>>> improve ease-of-use a lot.
>> 
>> Are we able to add some kind of type constraint which allows
>> append/prepend operations on a particular collection? Seems like a
>> good replacement for MutableCollection in this case. It should be
>> available to append elements greater or equal to the last element in
>> SortedArray, isn't it?
>
> I've been playing around with a protocol-based approach to these
> questions. A mutable sorted collection can easily allow operations
> that maintain the collection's order (basically just insertion with
> the collection deciding where to put the element or elements and
> removal of one or more elements). I suppose it's possible to allow
> appending / prepending if we require that the elements be (a) sorted
> and (b) wouldn't change the sort of the collection.

This would require (well, should use) a protocol that would be refined
by RangeReplaceableCollection, which means it needs to happen in before ABI
stability sets in.

> You can see my current version here:
> https://gist.github.com/natecook1000/9400edd75947fcf41dd4c82d1519dea8
> — it defines two protocols along with a mutable SortedArray and an
> immutable SortedView.

Cool; looking forward to the full proposal! ;-)


-- 
-Dave
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Dave Abrahams via swift-evolution]

on Mon Jan 30 2017, Alexey Komnin  wrote:

> Hello to everyone.
>
> Let me put my two cents.
>
>>> I didn’t want the SortedArray to conform to MutableCollection or
>>> even RandomAccessCollection as I felt it was not needed just to
>>> support binary search and prevent re-sorting.
>>
>> You are right not to support MutableCollection or
>> RangeReplaceableCollection, as those would allow you to violate the
>> “sorted” invariant.  However, it should conform to
>> RandomAccessCollection; that's really easy to implement and would
>> improve ease-of-use a lot.
>
> Are we able to add some kind of type constraint which allows
> append/prepend operations on a particular collection? Seems like a
> good replacement for MutableCollection in this case. It should be
> available to append elements greater or equal to the last element in
> SortedArray, isn't it?

I think we should handle that with a method like this

  /// Inserts `x` in the correct position, using `positionHint`
  /// to improve performance if it is accurate.
  func insert(_ x: Element, positionHint: Index) -> Index

>
>
> Regards,
> Alex Komnin.
>
> On Mon, Jan 30, 2017 at 3:21 AM, Dave Abrahams via swift-evolution
>  wrote:
>>
>> Hi Cihat,
>>
>> Thanks for diving in here!  For reference, here's the last thing I said
>> about this topic (IIRC):
>>
>> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html
>>
>> Also
>> https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift.gyb#L679
>>
>> Note: the comment there isn't quite right: 
>> 
>>
>> on Sun Jan 29 2017, Cihat Gündüz  wrote:
>>
>>> Hi guys, I know this topic is probably out of scope for Swift 4
>>> and a proposal was already rejected for Swift 3, but I’d like to share
>>> my two cents on this as I just wrote a SortedArray class with support
>>> for binary search in my open source library HandySwift.
>>>
>>> You can see my classes current implementation here:
>>> https://github.com/Flinesoft/HandySwift/blob/cd7ae7041c8174cd655f24eae653f76697875a48/Sources/Structs/SortedArray.swift
>>>
>>> My goal was to provide only what is commonly needed when working with
>>> big arrays in algorithms. For me this included:
>>>
>>> - having a type that keeps a sorted array to prevent re-sorting (solution: 
>>> the SortedArray class)
>>
>> Sounds consistent with my feedback... but it doesn't conform to
>> RandomAccessCollection.  Why not?
>>
>>> - have a method that can find an object using binary search (solution: the 
>>> index method)
>>
>> Please see the algorithms prototype
>>
>>> - allow partitioning the array into smaller parts (solution: subscript, 
>>> prefix & suffix methods)
>>
>> * The collection returned by the slicing subscript should obey the law
>>
>>  a[i..>
>>   Normally that means you want to make it a different type from a.
>>
>>> - prevent re-implementing the Array class (solution: a getter to the
>>>   stored internal array)
>>
>> Not sure I understand what this is supposed to mean.
>>
>>> Also note that the SortedArray in my approach allows all types that
>>> conform to `Sequence` as input with `Comparable` elements and saves
>>> them into a sorted array on initialization. That array is also
>>> publicly read-accessible. Inserting and deleting objects from the
>>> SortedArray are possible, too, but that’s just few of the
>>> MutableCollection methods.
>>
>> Actually no, those are RangeReplaceableCollection methods.
>>
>>> I didn’t want the SortedArray to conform to MutableCollection or
>>> even RandomAccessCollection as I felt it was not needed just to
>>> support binary search and prevent re-sorting.
>>
>> You are right not to support MutableCollection or
>> RangeReplaceableCollection, as those would allow you to violate the
>> “sorted” invariant.  However, it should conform to
>> RandomAccessCollection; that's really easy to implement and would
>> improve ease-of-use a lot.
>>
>>
>>> Maybe my approach can somehow help forming the final solution to be
>>> included into Swift once this features is tackled again.
>>>
>>> Best regards,
>>> Cihat
>>> ___
>>> swift-evolution mailing list
>>> swift-evolution@swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>
>>
>> --
>> -Dave
>>
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
-Dave
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Nate Cook via swift-evolution]

> On Jan 30, 2017, at 2:47 AM, Alexey Komnin via swift-evolution 
>  wrote:
> 
> Hello to everyone.
> 
> Let me put my two cents.
> 
>>> I didn’t want the SortedArray to conform to MutableCollection or
>>> even RandomAccessCollection as I felt it was not needed just to
>>> support binary search and prevent re-sorting.
>> 
>> You are right not to support MutableCollection or
>> RangeReplaceableCollection, as those would allow you to violate the
>> “sorted” invariant.  However, it should conform to
>> RandomAccessCollection; that's really easy to implement and would
>> improve ease-of-use a lot.
> 
> Are we able to add some kind of type constraint which allows
> append/prepend operations on a particular collection? Seems like a
> good replacement for MutableCollection in this case. It should be
> available to append elements greater or equal to the last element in
> SortedArray, isn't it?

I've been playing around with a protocol-based approach to these questions. A 
mutable sorted collection can easily allow operations that maintain the 
collection's order (basically just insertion with the collection deciding where 
to put the element or elements and removal of one or more elements). I suppose 
it's possible to allow appending / prepending if we require that the elements 
be (a) sorted and (b) wouldn't change the sort of the collection.

You can see my current version here: 
https://gist.github.com/natecook1000/9400edd75947fcf41dd4c82d1519dea8 — it 
defines two protocols along with a mutable SortedArray and an immutable 
SortedView.

-Nate


> Regards,
> Alex Komnin.
> 
> 
> 
> On Mon, Jan 30, 2017 at 3:21 AM, Dave Abrahams via swift-evolution
>  wrote:
>> 
>> Hi Cihat,
>> 
>> Thanks for diving in here!  For reference, here's the last thing I said
>> about this topic (IIRC):
>> 
>> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html
>> 
>> Also
>> https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift.gyb#L679
>> 
>> Note: the comment there isn't quite right: 
>> 
>> 
>> on Sun Jan 29 2017, Cihat Gündüz  wrote:
>> 
>>> Hi guys, I know this topic is probably out of scope for Swift 4
>>> and a proposal was already rejected for Swift 3, but I’d like to share
>>> my two cents on this as I just wrote a SortedArray class with support
>>> for binary search in my open source library HandySwift.
>>> 
>>> You can see my classes current implementation here:
>>> https://github.com/Flinesoft/HandySwift/blob/cd7ae7041c8174cd655f24eae653f76697875a48/Sources/Structs/SortedArray.swift
>>> 
>>> My goal was to provide only what is commonly needed when working with
>>> big arrays in algorithms. For me this included:
>>> 
>>> - having a type that keeps a sorted array to prevent re-sorting (solution: 
>>> the SortedArray class)
>> 
>> Sounds consistent with my feedback... but it doesn't conform to
>> RandomAccessCollection.  Why not?
>> 
>>> - have a method that can find an object using binary search (solution: the 
>>> index method)
>> 
>> Please see the algorithms prototype
>> 
>>> - allow partitioning the array into smaller parts (solution: subscript, 
>>> prefix & suffix methods)
>> 
>> * The collection returned by the slicing subscript should obey the law
>> 
>> a[i..> 
>>  Normally that means you want to make it a different type from a.
>> 
>>> - prevent re-implementing the Array class (solution: a getter to the
>>>  stored internal array)
>> 
>> Not sure I understand what this is supposed to mean.
>> 
>>> Also note that the SortedArray in my approach allows all types that
>>> conform to `Sequence` as input with `Comparable` elements and saves
>>> them into a sorted array on initialization. That array is also
>>> publicly read-accessible. Inserting and deleting objects from the
>>> SortedArray are possible, too, but that’s just few of the
>>> MutableCollection methods.
>> 
>> Actually no, those are RangeReplaceableCollection methods.
>> 
>>> I didn’t want the SortedArray to conform to MutableCollection or
>>> even RandomAccessCollection as I felt it was not needed just to
>>> support binary search and prevent re-sorting.
>> 
>> You are right not to support MutableCollection or
>> RangeReplaceableCollection, as those would allow you to violate the
>> “sorted” invariant.  However, it should conform to
>> RandomAccessCollection; that's really easy to implement and would
>> improve ease-of-use a lot.
>> 
>> 
>>> Maybe my approach can somehow help forming the final solution to be
>>> included into Swift once this features is tackled again.
>>> 
>>> Best regards,
>>> Cihat
>>> ___
>>> swift-evolution mailing list
>>> swift-evolution@swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>> 
>> 
>> --
>> -Dave
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Alexey Komnin via swift-evolution]

Hello to everyone.

Let me put my two cents.

>> I didn’t want the SortedArray to conform to MutableCollection or
>> even RandomAccessCollection as I felt it was not needed just to
>> support binary search and prevent re-sorting.
>
> You are right not to support MutableCollection or
> RangeReplaceableCollection, as those would allow you to violate the
> “sorted” invariant.  However, it should conform to
> RandomAccessCollection; that's really easy to implement and would
> improve ease-of-use a lot.

Are we able to add some kind of type constraint which allows
append/prepend operations on a particular collection? Seems like a
good replacement for MutableCollection in this case. It should be
available to append elements greater or equal to the last element in
SortedArray, isn't it?

Regards,
Alex Komnin.



On Mon, Jan 30, 2017 at 3:21 AM, Dave Abrahams via swift-evolution
 wrote:
>
> Hi Cihat,
>
> Thanks for diving in here!  For reference, here's the last thing I said
> about this topic (IIRC):
>
> https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html
>
> Also
> https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift.gyb#L679
>
> Note: the comment there isn't quite right: 
> 
>
> on Sun Jan 29 2017, Cihat Gündüz  wrote:
>
>> Hi guys, I know this topic is probably out of scope for Swift 4
>> and a proposal was already rejected for Swift 3, but I’d like to share
>> my two cents on this as I just wrote a SortedArray class with support
>> for binary search in my open source library HandySwift.
>>
>> You can see my classes current implementation here:
>> https://github.com/Flinesoft/HandySwift/blob/cd7ae7041c8174cd655f24eae653f76697875a48/Sources/Structs/SortedArray.swift
>>
>> My goal was to provide only what is commonly needed when working with
>> big arrays in algorithms. For me this included:
>>
>> - having a type that keeps a sorted array to prevent re-sorting (solution: 
>> the SortedArray class)
>
> Sounds consistent with my feedback... but it doesn't conform to
> RandomAccessCollection.  Why not?
>
>> - have a method that can find an object using binary search (solution: the 
>> index method)
>
> Please see the algorithms prototype
>
>> - allow partitioning the array into smaller parts (solution: subscript, 
>> prefix & suffix methods)
>
> * The collection returned by the slicing subscript should obey the law
>
>  a[i..
>   Normally that means you want to make it a different type from a.
>
>> - prevent re-implementing the Array class (solution: a getter to the
>>   stored internal array)
>
> Not sure I understand what this is supposed to mean.
>
>> Also note that the SortedArray in my approach allows all types that
>> conform to `Sequence` as input with `Comparable` elements and saves
>> them into a sorted array on initialization. That array is also
>> publicly read-accessible. Inserting and deleting objects from the
>> SortedArray are possible, too, but that’s just few of the
>> MutableCollection methods.
>
> Actually no, those are RangeReplaceableCollection methods.
>
>> I didn’t want the SortedArray to conform to MutableCollection or
>> even RandomAccessCollection as I felt it was not needed just to
>> support binary search and prevent re-sorting.
>
> You are right not to support MutableCollection or
> RangeReplaceableCollection, as those would allow you to violate the
> “sorted” invariant.  However, it should conform to
> RandomAccessCollection; that's really easy to implement and would
> improve ease-of-use a lot.
>
>
>> Maybe my approach can somehow help forming the final solution to be
>> included into Swift once this features is tackled again.
>>
>> Best regards,
>> Cihat
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>
> --
> -Dave
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Dave Abrahams via swift-evolution]

Hi Cihat,

Thanks for diving in here!  For reference, here's the last thing I said
about this topic (IIRC):

https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160502/016729.html

Also
https://github.com/apple/swift/blob/master/test/Prototypes/Algorithms.swift.gyb#L679

Note: the comment there isn't quite right: 


on Sun Jan 29 2017, Cihat Gündüz  wrote:

> Hi guys, I know this topic is probably out of scope for Swift 4 
> and a proposal was already rejected for Swift 3, but I’d like to share
> my two cents on this as I just wrote a SortedArray class with support
> for binary search in my open source library HandySwift.
>
> You can see my classes current implementation here:
> https://github.com/Flinesoft/HandySwift/blob/cd7ae7041c8174cd655f24eae653f76697875a48/Sources/Structs/SortedArray.swift
>
> My goal was to provide only what is commonly needed when working with
> big arrays in algorithms. For me this included:
>
> - having a type that keeps a sorted array to prevent re-sorting (solution: 
> the SortedArray class)

Sounds consistent with my feedback... but it doesn't conform to
RandomAccessCollection.  Why not?

> - have a method that can find an object using binary search (solution: the 
> index method)

Please see the algorithms prototype

> - allow partitioning the array into smaller parts (solution: subscript, 
> prefix & suffix methods)

* The collection returned by the slicing subscript should obey the law

 a[i.. - prevent re-implementing the Array class (solution: a getter to the
>   stored internal array)

Not sure I understand what this is supposed to mean.

> Also note that the SortedArray in my approach allows all types that
> conform to `Sequence` as input with `Comparable` elements and saves
> them into a sorted array on initialization. That array is also
> publicly read-accessible. Inserting and deleting objects from the
> SortedArray are possible, too, but that’s just few of the
> MutableCollection methods. 

Actually no, those are RangeReplaceableCollection methods.  

> I didn’t want the SortedArray to conform to MutableCollection or
> even RandomAccessCollection as I felt it was not needed just to
> support binary search and prevent re-sorting.

You are right not to support MutableCollection or
RangeReplaceableCollection, as those would allow you to violate the
“sorted” invariant.  However, it should conform to
RandomAccessCollection; that's really easy to implement and would
improve ease-of-use a lot.


> Maybe my approach can somehow help forming the final solution to be
> included into Swift once this features is tackled again.
>
> Best regards,
> Cihat
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[swift-evolution] [Proposal] Add Array binary search to the standard library

[Cihat Gündüz via swift-evolution]

Hi guys, I know this topic is probably out of scope for Swift 4 and a proposal 
was already rejected for Swift 3, but I’d like to share my two cents on this as 
I just wrote a SortedArray class with support for binary search in my open 
source library HandySwift.

You can see my classes current implementation here:
https://github.com/Flinesoft/HandySwift/blob/cd7ae7041c8174cd655f24eae653f76697875a48/Sources/Structs/SortedArray.swift

My goal was to provide only what is commonly needed when working with big 
arrays in algorithms. For me this included:
- having a type that keeps a sorted array to prevent re-sorting (solution: the 
SortedArray class)
- have a method that can find an object using binary search (solution: the 
index method)
- allow partitioning the array into smaller parts (solution: subscript, prefix 
& suffix methods)
- prevent re-implementing the Array class (solution: a getter to the stored 
internal array)

Also note that the SortedArray in my approach allows all types that conform to 
`Sequence` as input with `Comparable` elements and saves them into a sorted 
array on initialization. That array is also publicly read-accessible. Inserting 
and deleting objects from the SortedArray are possible, too, but that’s just 
few of the MutableCollection methods. I didn’t want the SortedArray to conform 
to MutableCollection or even RandomAccessCollection as I felt it was not needed 
just to support binary search and prevent re-sorting.

Maybe my approach can somehow help forming the final solution to be included 
into Swift once this features is tackled again.

Best regards,
Cihat
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Dave Abrahams via swift-evolution]

on Wed Sep 07 2016, Xiaodi Wu  wrote:

> Hi Igor,
>
> Since your proposal would be additive, it probably wouldn't be considered
> for review until the next phase of Swift evolution.
>
> My read of the core team's feedback is that some binary search
> functionality is welcome, but it's a question of *how* it's designed. When
> purely additive changes are in scope, a successful proposal will likely
> address the weaknesses of the previous proposal. Since that proposal
> considered as an alternative a design such as yours, but it concluded that
> a different design was better, you'll probably want to address why you
> think this API design is best, or alternatively, you may want to study the
> alternatives presented in that proposal and refine them to be better.

+1 to all that.  Also, this is not Array-specific; it applies to any
random-access collection at least, and arguably to any collection at
all.

> On Wed, Sep 7, 2016 at 05:16 Igor Vasilenko via swift-evolution <
> swift-evolution@swift.org> wrote:
>
>> do you mean this?
>>
>> public func binarySearch(array: [T], key: T, range: 
>> Range, sorted: Bool) -> Int?
>>
>> Best regards, Igor Vasilenko
>>
>> iOS Developer at Yota
>>
>> +7 (999) 527 - 07 - 59
>> spb.vasile...@gmail.com 
>> 
>> www.spbvasilenko.github.io 
>>
>>
>>
>>
>>
>>
>>
>>
>> On 07 Sep 2016, at 13:08, Guillaume DIDIER <
>> guillaume.didier.2...@polytechnique.org> wrote:
>>
>> Basically for a binary search to work it needs to operate on a sorted
>> array (it is a necessary invariant).
>>
>> It is really interesting when you make a lot of search in the same sorted
>> array, hence I would +1 the sorted array, with initializer from an array.
>>
>>
>> *Guillaume  DIDIER*
>> —
>> *ÉCOLE POLYTECHNIQUE*
>> 91128 PALAISEAU CEDEX
>> M. +33 (0)7 70 43 18 40
>> guillaume.did...@polytechnique.edu
>> 
>> www.polytechnique.edu
>> —
>>
>> Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution <
>> swift-evolution@swift.org> a écrit :
>>
>>
>> On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution <
>> swift-evolution@swift.org> wrote:
>>
>> Aside from this being additive (i.e. out of scope for Swift 4), this
>> requires the array to be sorted in order for the search to work - who will
>> guarantee this? The caller? What happens when this is called on an array
>> that is not sorted? You likely get nil, while the item is in the array
>> (false negative).
>>
>> This would probably make sense by not extending Array itself, but
>> introducing SortedArray which would automatically keep its members sorted
>> instead - this way there would be a guarantee that the array is sorted and
>> the user won't have to deal with sorting the array. It would however be at
>> the cost of O(log N) for insertion…
>>
>>
>> I don't think this is really a problem, just needs to be clear that
>> behaviour is undefined if the array wasn't previously sorted (or not in the
>> same order).
>>
>> On this topic there was a previous proposal that was undergoing
>> refinements after being initially rejected, you can find it here:
>>
>> https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
>>
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Xiaodi Wu via swift-evolution]

Hi Igor,

Since your proposal would be additive, it probably wouldn't be considered
for review until the next phase of Swift evolution.

My read of the core team's feedback is that some binary search
functionality is welcome, but it's a question of *how* it's designed. When
purely additive changes are in scope, a successful proposal will likely
address the weaknesses of the previous proposal. Since that proposal
considered as an alternative a design such as yours, but it concluded that
a different design was better, you'll probably want to address why you
think this API design is best, or alternatively, you may want to study the
alternatives presented in that proposal and refine them to be better.
On Wed, Sep 7, 2016 at 05:16 Igor Vasilenko via swift-evolution <
swift-evolution@swift.org> wrote:

> do you mean this?
>
> public func binarySearch(array: [T], key: T, range: 
> Range, sorted: Bool) -> Int?
>
> Best regards, Igor Vasilenko
>
> iOS Developer at Yota
>
> +7 (999) 527 - 07 - 59
> spb.vasile...@gmail.com 
> www.spbvasilenko.github.io 
>
>
>
>
>
>
>
>
> On 07 Sep 2016, at 13:08, Guillaume DIDIER <
> guillaume.didier.2...@polytechnique.org> wrote:
>
> Basically for a binary search to work it needs to operate on a sorted
> array (it is a necessary invariant).
>
> It is really interesting when you make a lot of search in the same sorted
> array, hence I would +1 the sorted array, with initializer from an array.
>
>
> *Guillaume  DIDIER*
> —
> *ÉCOLE POLYTECHNIQUE*
> 91128 PALAISEAU CEDEX
> M. +33 (0)7 70 43 18 40
> guillaume.did...@polytechnique.edu
> 
> www.polytechnique.edu
> —
>
> Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution <
> swift-evolution@swift.org> a écrit :
>
>
> On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution <
> swift-evolution@swift.org> wrote:
>
> Aside from this being additive (i.e. out of scope for Swift 4), this
> requires the array to be sorted in order for the search to work - who will
> guarantee this? The caller? What happens when this is called on an array
> that is not sorted? You likely get nil, while the item is in the array
> (false negative).
>
> This would probably make sense by not extending Array itself, but
> introducing SortedArray which would automatically keep its members sorted
> instead - this way there would be a guarantee that the array is sorted and
> the user won't have to deal with sorting the array. It would however be at
> the cost of O(log N) for insertion…
>
>
> I don't think this is really a problem, just needs to be clear that
> behaviour is undefined if the array wasn't previously sorted (or not in the
> same order).
>
> On this topic there was a previous proposal that was undergoing
> refinements after being initially rejected, you can find it here:
>
> https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
>
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Igor Vasilenko via swift-evolution]

do you mean this?
public func binarySearch(array: [T], key: T, range: Range, 
sorted: Bool) -> Int?
Best regards, Igor Vasilenko 

iOS Developer at Yota

+7 (999) 527 - 07 - 59
spb.vasile...@gmail.com 
www.spbvasilenko.github.io 







> On 07 Sep 2016, at 13:08, Guillaume DIDIER 
>  wrote:
> 
> Basically for a binary search to work it needs to operate on a sorted array 
> (it is a necessary invariant).
> 
> It is really interesting when you make a lot of search in the same sorted 
> array, hence I would +1 the sorted array, with initializer from an array.
> 
> 
> Guillaume  DIDIER
> —
> ÉCOLE POLYTECHNIQUE
> 91128 PALAISEAU CEDEX
> M. +33 (0)7 70 43 18 40
> guillaume.did...@polytechnique.edu 
> 
> www.polytechnique.edu 
> —
> 
>> Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution 
>> mailto:swift-evolution@swift.org>> a écrit :
>> 
>> 
>>> On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution 
>>> mailto:swift-evolution@swift.org>> wrote:
>>> 
>>> Aside from this being additive (i.e. out of scope for Swift 4), this 
>>> requires the array to be sorted in order for the search to work - who will 
>>> guarantee this? The caller? What happens when this is called on an array 
>>> that is not sorted? You likely get nil, while the item is in the array 
>>> (false negative).
>>> 
>>> This would probably make sense by not extending Array itself, but 
>>> introducing SortedArray which would automatically keep its members sorted 
>>> instead - this way there would be a guarantee that the array is sorted and 
>>> the user won't have to deal with sorting the array. It would however be at 
>>> the cost of O(log N) for insertion…
>> 
>> I don't think this is really a problem, just needs to be clear that 
>> behaviour is undefined if the array wasn't previously sorted (or not in the 
>> same order).
>> 
>> On this topic there was a previous proposal that was undergoing refinements 
>> after being initially rejected, you can find it here:
>> https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
>>  
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Igor Vasilenko via swift-evolution]

This is mean that my PR/proposal will be as duplicate previous rejected 
proposal?  
Or my proposal have a good chance for accept? 
Best regards, Igor Vasilenko 

iOS Developer at Yota

+7 (999) 527 - 07 - 59
spb.vasile...@gmail.com 
www.spbvasilenko.github.io 







> On 07 Sep 2016, at 13:04, Haravikk  wrote:
> 
> 
>> On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution 
>>  wrote:
>> 
>> Aside from this being additive (i.e. out of scope for Swift 4), this 
>> requires the array to be sorted in order for the search to work - who will 
>> guarantee this? The caller? What happens when this is called on an array 
>> that is not sorted? You likely get nil, while the item is in the array 
>> (false negative).
>> 
>> This would probably make sense by not extending Array itself, but 
>> introducing SortedArray which would automatically keep its members sorted 
>> instead - this way there would be a guarantee that the array is sorted and 
>> the user won't have to deal with sorting the array. It would however be at 
>> the cost of O(log N) for insertion…
> 
> I don't think this is really a problem, just needs to be clear that behaviour 
> is undefined if the array wasn't previously sorted (or not in the same order).
> 
> On this topic there was a previous proposal that was undergoing refinements 
> after being initially rejected, you can find it here:
> https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Guillaume DIDIER via swift-evolution]

Basically for a binary search to work it needs to operate on a sorted array (it 
is a necessary invariant).

It is really interesting when you make a lot of search in the same sorted 
array, hence I would +1 the sorted array, with initializer from an array.


Guillaume  DIDIER
—
ÉCOLE POLYTECHNIQUE
91128 PALAISEAU CEDEX
M. +33 (0)7 70 43 18 40
guillaume.did...@polytechnique.edu 

www.polytechnique.edu 
—

> Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution 
>  a écrit :
> 
> 
>> On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution 
>>  wrote:
>> 
>> Aside from this being additive (i.e. out of scope for Swift 4), this 
>> requires the array to be sorted in order for the search to work - who will 
>> guarantee this? The caller? What happens when this is called on an array 
>> that is not sorted? You likely get nil, while the item is in the array 
>> (false negative).
>> 
>> This would probably make sense by not extending Array itself, but 
>> introducing SortedArray which would automatically keep its members sorted 
>> instead - this way there would be a guarantee that the array is sorted and 
>> the user won't have to deal with sorting the array. It would however be at 
>> the cost of O(log N) for insertion…
> 
> I don't think this is really a problem, just needs to be clear that behaviour 
> is undefined if the array wasn't previously sorted (or not in the same order).
> 
> On this topic there was a previous proposal that was undergoing refinements 
> after being initially rejected, you can find it here:
> https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Haravikk via swift-evolution]

> On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution 
>  wrote:
> 
> Aside from this being additive (i.e. out of scope for Swift 4), this requires 
> the array to be sorted in order for the search to work - who will guarantee 
> this? The caller? What happens when this is called on an array that is not 
> sorted? You likely get nil, while the item is in the array (false negative).
> 
> This would probably make sense by not extending Array itself, but introducing 
> SortedArray which would automatically keep its members sorted instead - this 
> way there would be a guarantee that the array is sorted and the user won't 
> have to deal with sorting the array. It would however be at the cost of O(log 
> N) for insertion…

I don't think this is really a problem, just needs to be clear that behaviour 
is undefined if the array wasn't previously sorted (or not in the same order).

On this topic there was a previous proposal that was undergoing refinements 
after being initially rejected, you can find it here:
https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Igor Vasilenko via swift-evolution]

In my mind, caller should be guarantee that array is sorted. As an example, in 
Objective-C SDK, NSArray should be is sorted before for using binary search 
method.
But this is a good idea to make a SortedArray. 
Best regards, Igor Vasilenko 

iOS Developer at Yota

+7 (999) 527 - 07 - 59
spb.vasile...@gmail.com 
www.spbvasilenko.github.io 







> On 07 Sep 2016, at 12:08, Charlie Monroe  wrote:
> 
> Aside from this being additive (i.e. out of scope for Swift 4), this requires 
> the array to be sorted in order for the search to work - who will guarantee 
> this? The caller? What happens when this is called on an array that is not 
> sorted? You likely get nil, while the item is in the array (false negative).
> 
> This would probably make sense by not extending Array itself, but introducing 
> SortedArray which would automatically keep its members sorted instead - this 
> way there would be a guarantee that the array is sorted and the user won't 
> have to deal with sorting the array. It would however be at the cost of O(log 
> N) for insertion...
> 
>> On Sep 7, 2016, at 10:59 AM, Igor Vasilenko via swift-evolution 
>> mailto:swift-evolution@swift.org>> wrote:
>> 
>> Introduction
>> 
>> Right now, for Array implemented array.contains(element) and 
>> array.indexOf(element)for searching in an array. Both of these methods 
>> iterate over all elements in the array, starting at index 0, until they find 
>> a match. In the worst case (there is no match), they have to iterate over 
>> the entire array. In big O notation, the methods’ performance characteristic 
>> is O(n). This is usually not a problem for small arrays with only a few 
>> dozen elements. But if your code regularly needs to find objects in arrays 
>> with thousands of elements, you may want to look for a faster search 
>> algorithm.
>> 
>> Motivation
>> 
>> If the array is sorted by the search key, binary search can give you a huge 
>> boost in performance. By comparing the middle element in the array to the 
>> search item, the algorithm effectively halves the number of elements it has 
>> to search trough with each iteration. Binary search has O(log n) 
>> performance. What does this mean in practice? Searching a sorted array of 
>> 100,000 elements using binary search would require at most 17 comparisons 
>> compared to the 50,000 comparisons a naive linear search would take on 
>> average.
>> 
>> Detailed design
>> 
>> public func binarySearch(array: [T], key: T, range: 
>> Range) -> Int? {
>> if range.startIndex >= range.endIndex {
>> return nil
>> } else {
>> let midIndex = range.endIndex + (range.endIndex - range.startIndex) 
>> / 2
>> if array[midIndex] > key {
>> return binarySearch(array, key: key, range: range.startIndex ..< 
>> midIndex)
>> } else if array[midIndex] < key {
>> return binarySearch(array, key: key, range: midIndex + 1 ..< 
>> range.endIndex)
>> } else {
>> return midIndex
>> }
>> }
>> }
>> 
>> let numbers = [1, 2, 3, 4, 5]
>> binarySearch(numbers, key: 3, range: 1 ..< numbers.count)
>> Best regards, Igor Vasilenko 
>> 
>> iOS Developer at Yota
>> 
>> spb.vasile...@gmail.com 
>> 
>> 
>> 
>> 
>> 
>> 
>> 
>> 
>> ___
>> swift-evolution mailing list
>> swift-evolution@swift.org 
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Re: [swift-evolution] [Proposal] Add Array binary search to the standard library

[Charlie Monroe via swift-evolution]

Aside from this being additive (i.e. out of scope for Swift 4), this requires 
the array to be sorted in order for the search to work - who will guarantee 
this? The caller? What happens when this is called on an array that is not 
sorted? You likely get nil, while the item is in the array (false negative).

This would probably make sense by not extending Array itself, but introducing 
SortedArray which would automatically keep its members sorted instead - this 
way there would be a guarantee that the array is sorted and the user won't have 
to deal with sorting the array. It would however be at the cost of O(log N) for 
insertion...

> On Sep 7, 2016, at 10:59 AM, Igor Vasilenko via swift-evolution 
>  wrote:
> 
> Introduction
> 
> Right now, for Array implemented array.contains(element) and 
> array.indexOf(element)for searching in an array. Both of these methods 
> iterate over all elements in the array, starting at index 0, until they find 
> a match. In the worst case (there is no match), they have to iterate over the 
> entire array. In big O notation, the methods’ performance characteristic is 
> O(n). This is usually not a problem for small arrays with only a few dozen 
> elements. But if your code regularly needs to find objects in arrays with 
> thousands of elements, you may want to look for a faster search algorithm.
> 
> Motivation
> 
> If the array is sorted by the search key, binary search can give you a huge 
> boost in performance. By comparing the middle element in the array to the 
> search item, the algorithm effectively halves the number of elements it has 
> to search trough with each iteration. Binary search has O(log n) performance. 
> What does this mean in practice? Searching a sorted array of 100,000 elements 
> using binary search would require at most 17 comparisons compared to the 
> 50,000 comparisons a naive linear search would take on average.
> 
> Detailed design
> 
> public func binarySearch(array: [T], key: T, range: 
> Range) -> Int? {
> if range.startIndex >= range.endIndex {
> return nil
> } else {
> let midIndex = range.endIndex + (range.endIndex - range.startIndex) / 
> 2
> if array[midIndex] > key {
> return binarySearch(array, key: key, range: range.startIndex ..< 
> midIndex)
> } else if array[midIndex] < key {
> return binarySearch(array, key: key, range: midIndex + 1 ..< 
> range.endIndex)
> } else {
> return midIndex
> }
> }
> }
> 
> let numbers = [1, 2, 3, 4, 5]
> binarySearch(numbers, key: 3, range: 1 ..< numbers.count)
> Best regards, Igor Vasilenko 
> 
> iOS Developer at Yota
> 
> spb.vasile...@gmail.com 
> 
> 
> 
> 
> 
> 
> 
> 
> ___
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

[swift-evolution] [Proposal] Add Array binary search to the standard library

[Igor Vasilenko via swift-evolution]

Introduction

Right now, for Array implemented array.contains(element) and 
array.indexOf(element)for searching in an array. Both of these methods iterate 
over all elements in the array, starting at index 0, until they find a match. 
In the worst case (there is no match), they have to iterate over the entire 
array. In big O notation, the methods’ performance characteristic is O(n). This 
is usually not a problem for small arrays with only a few dozen elements. But 
if your code regularly needs to find objects in arrays with thousands of 
elements, you may want to look for a faster search algorithm.

Motivation

If the array is sorted by the search key, binary search can give you a huge 
boost in performance. By comparing the middle element in the array to the 
search item, the algorithm effectively halves the number of elements it has to 
search trough with each iteration. Binary search has O(log n) performance. What 
does this mean in practice? Searching a sorted array of 100,000 elements using 
binary search would require at most 17 comparisons compared to the 50,000 
comparisons a naive linear search would take on average.

Detailed design

public func binarySearch(array: [T], key: T, range: Range) 
-> Int? {
if range.startIndex >= range.endIndex {
return nil
} else {
let midIndex = range.endIndex + (range.endIndex - range.startIndex) / 2
if array[midIndex] > key {
return binarySearch(array, key: key, range: range.startIndex ..< 
midIndex)
} else if array[midIndex] < key {
return binarySearch(array, key: key, range: midIndex + 1 ..< 
range.endIndex)
} else {
return midIndex
}
}
}

let numbers = [1, 2, 3, 4, 5]
binarySearch(numbers, key: 3, range: 1 ..< numbers.count)
Best regards, Igor Vasilenko 

iOS Developer at Yota

spb.vasile...@gmail.com 








___
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution