[swift-evolution] [Draft] Expanded min/max algorithms

[Nate Cook]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160417/5fd58780/attachment.html>