Hi Nate, I think this is a very useful addition! I also had a related proposal few days ago: https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160411/014665.html <https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160411/014665.html> I feel like min/max extension and element order belong to the same family of enhancements. If you are interested, maybe we can combine them together into a single proposal?
Best, Taras > On 17 Apr 2016, at 08:44, Nate Cook via swift-evolution > <swift-evolution@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@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