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.
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:
···
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…
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 <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.
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).
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
On 07 Sep 2016, at 12:08, Charlie Monroe <charlie@charliemonroe.net> 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 <swift-evolution@swift.org <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.
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
On 07 Sep 2016, at 13:04, Haravikk <swift-evolution@haravikk.me> wrote:
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).
Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :
On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution <swift-evolution@swift.org <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).
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:
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:
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 07 2016, Xiaodi Wu <swift-evolution@swift.org> wrote:
On Wed, Sep 7, 2016 at 05:16 Igor Vasilenko via swift-evolution < > swift-evolution@swift.org> wrote:
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: