[swift-evolution] [Draft] Expanded min/max algorithms
plx
plxswift at icloud.com
Sun Apr 17 08:46:21 CDT 2016
I like the idea. It worries me a bit if the general recipe for such situations is to add dedicated-purpose methods like `_customIndexOfMinComparableElement` (etc.) to standard-library protocols; it *will* work, but is only going to work for the methods that get such treatment.
If it were feasible, I’d *greatly* prefer having some more-general way to (conditionally?) add overridable methods to a protocol, e.g.:
// made-up declaration, all declared methods below are now overridable
// on suitable types
overridable extension Collection where Iterator.Element: Comparable {
func min() -> Iterator.Element?
}
…but am not sure that’s even realistically possible.
The reason I bring it up is that I’d hope that `indexOf`, `contains`, and also `upperBound`/`lowerBound` would merit a similar treatment to that proposed here for min, max, and minmax (if not already given such; if they get added to standard-library; etc.).
Moving on, wrt these min/max elements themselves: I think any expectation about *which* index gets returned should be document—either no such expectation in general, or a specific expectation, or that each concrete collection should document the expectation, etc.—because for the minIndex/maxIndex methods different approaches can yield different results.
EG: consider an order-maintaining collection that has contents ~ `[1,1,1,2,2,2,3,3,3]`. There are multiple candidates for both `minIndex` and `maxIndex`.
I don’t have a strong opinion on what the right preference would be here, but I think whatever the behavior winds up being should be at least documented.
Finally, FWIW if more of these semi-hidden methods become something exposed to users (as “advanced” options, perhaps, but still) I think replacing `??` with something like
enum AdvancedCustomizationPointResult<T> {
case NotCustomized // like `nil` for ??
case NoResult // like `Optional(nil)` for ??
case Result(T) // like `Optional(T)` for ??
}
…might be worth considering (except with a better name than that). I’m not trying to backdoor optional protocol methods or anything, it just seems advisable to more-explicitly represent the intent (?? certainly works but feels a bit obscure).
> On Apr 17, 2016, at 1:44 AM, Nate Cook via swift-evolution <swift-evolution at swift.org> wrote:
>
> Hello all,
>
> Attached is a draft of a proposal to expand the min and max sequence APIs to better handle collections and to support future sorted sequences/collections. The proposal is in a gist here <https://gist.github.com/natecook1000/d51267a6cf9e9463b9387bced4c65b16> and inlined below—would love to hear any comments or feedback before submitting the proposal.
>
> Nate
>
>
> Proposal: Expanded min/max algorithms
> This proposal would expand on the min() and max() sequence methods to add methods that return the corresponding index for a collection, efficiently find the minimum and maximum elements or indices at the same time, and provide extension points for sorted collections to provide all these results more efficiently.
>
> Related Bugs: SR-889 <https://bugs.swift.org/browse/SR-889> and SR-890 <https://bugs.swift.org/browse/SR-890>
> Motivation
> The Sequence protocol currently offers min() and max() methods that return the minimum and maximum elements of a sequence or collection. Unfortunately, there are applications where these methods do not provide enough flexibility to be useful.
>
> First, if the user of a collection wants not just to get the minimum value but also to operate on it in some way (e.g., mutation or just accessing it multiple times), she would need the index of the minimum element. The current APIs don't support that, so she would need to write her own.
>
> Second, the writer of a sorted collection is currently unable to provide efficient responses to the min() and max() methods when used in a generic context, even though these should be O(1) operations. Just like Set can respond quickly to contains(_:) even in a generic context, so too should new sorted collections be able to optimize their responses.
>
> Finally, getting the minimum and maximum elements (or indices) of a collection or sequence currently requires calling both min() and max(). With two calls, every element is iterated and compared twice. When you need both results, finding both the minimum and the maximum at the same time is more efficient, requiring only a single pass and 25% fewer comparisons.
>
> Proposed solution
> This proposal has three parts:
>
> Adding minIndex() and maxIndex() methods to Collection that return the index of the minimum and maximum elements, respectively.
>
> let numbers = [30, 40, 10, 20, 60, 50]
>
> if let i = numbers.minIndex() {
> print("\(i): \(numbers[i])") // 2: 10
> }
> Adding minmax() and minmaxIndices() methods to Sequence and Collection, respectively, to calculate the values (or indices) of the minimum and maximum elements simultaneously.
>
> if let result = numbers.minmax() {
> // result == (minimum: 10, maximum: 60)
> // ...
> }
> if let i = numbers.minmaxIndices() {
> // i == (minimum: 2, maximum: 4)
> print("\(i.minimum): \(numbers[i.minimum])")
> }
> Adding customization points for sequences and collections that can offer more efficient results: _customMinComparableElement()/_customMaxComparableElement() for Sequence and _customIndexOfMinComparableElement()/_customIndexOfMaxComparableElement()for Collection.
>
> Detailed design
> The following methods would be added to the visible public APIs of Sequence and Collection as default implementations.
>
> extension Sequence {
> /// Returns the minimum and maximum values of `self`, using
> /// `isOrderedBefore` to compare elements, or `nil` if the sequence
> /// has no elements.
> func minmax(@noescape isOrderedBefore isOrderedBefore:
> (Iterator.Element, Iterator.Element) throws -> Bool
> ) rethrows -> (min: Iterator.Element, max: Iterator.Element)?
> }
>
> extension Sequence where Iterator.Element: Comparable {
> /// Returns the minimum and maximum values of `self`, or `nil`
> /// if the sequence has no elements.
> func minmax() -> (min: Iterator.Element, max: Iterator.Element)?
> }
>
> extension Collection {
> /// Returns the index of the minimum element of `self`, using
> /// `isOrderedBefore` to compare elements, or `nil` if the
> /// collection has no elements.
> func minIndex(@noescape isOrderedBefore isOrderedBefore:
> (Iterator.Element, Iterator.Element) throws -> Bool
> ) rethrows -> Index?
>
> /// Returns the index of the maximum element of `self`, using
> /// `isOrderedBefore` to compare elements, or `nil` if the
> /// collection has no elements.
> func maxIndex(@noescape isOrderedBefore isOrderedBefore:
> (Iterator.Element, Iterator.Element) throws -> Bool
> ) rethrows -> Index?
>
> /// Returns the indices of the minimum and maximum elements of `self`,
> /// using `isOrderedBefore` to compare elements, or `nil` if the
> /// collection has no elements.
> func minmaxIndices(@noescape isOrderedBefore isOrderedBefore:
> (Iterator.Element, Iterator.Element) throws -> Bool
> ) rethrows -> (minIndex: Index, maxIndex: Index)?
> }
>
> extension Collection where Iterator.Element: Comparable {
> /// Returns the index of the minimum element of `self`, or `nil`
> /// if the collection has no elements.
> func minIndex() -> Index?
>
> /// Returns the index of the maximum element of `self`, or `nil`
> /// if the collection has no elements.
> func maxIndex() -> Index?
>
> /// Returns the indices of the minimum and maximum elements of `self`,
> /// or `nil` if the collection has no elements.
> func minmaxIndices() -> (minIndex: Index, maxIndex: Index)?
> }
> The customization points would be added to Sequence and Collection as protocol requirements, along with default implementations that return nil. The existing min()and max() methods would be updated to call the corresponding methods before iterating over the entire sequence.
>
> protocol Sequence {
> // ...
>
> /// Returns the minimum element as `Optional(element)` or `Optional(nil)`
> /// if the sequence has no elements. The uncustomized version returns
> /// `nil`.
> func _customMinComparableElement() -> Iterator.Element??
>
> /// Returns the maximum element as `Optional(element)` or `Optional(nil)`
> /// if the sequence has no elements. The uncustomized version returns
> /// `nil`.
> func _customMaxComparableElement() -> Iterator.Element??
> }
>
> protocol Collection {
> // ...
>
> /// Returns the index of the minimum element as `Optional(index)` or
> /// `Optional(nil)` if the sequence has no elements. The uncustomized
> /// version returns `nil`.
> func _customIndexOfMinComparableElement() -> Index??
>
> /// Returns the index of the maximum element as `Optional(index)` or
> /// `Optional(nil)` if the sequence has no elements. The uncustomized
> /// version returns `nil`.
> func _customIndexOfMaxComparableElement() -> Index??
> }
> Minmax Algorithm
>
> The minmax() algorithm finds the minimum and maximum elements of a sequence in one pass more efficiently than consecutive calls to min() and max(). This optimization comes from iterating over a sequence two elements at a time.
>
> In each iteration, two consecutive elements are compared with each other. Only the lesser element could be a minimum for the whole sequence, so it is compared with the current minimum, while only the greater element could be a maximum, so it is compared with the current maximum. This works out to 3 comparisons for every 2 elements vs. 2 comparisons for every element when the minimum and maximum are found individually.
>
> Impact on existing code
> As new APIs these should have no effect on existing code.
>
> Alternatives considered
> None.
>
> _______________________________________________
> 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/20160417/4aaf64e8/attachment.html>
More information about the swift-evolution
mailing list