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
