on Tue Apr 19 2016, Karl Wagner <swift-evolution@swift.org> wrote: > I understand what you’re saying about API bloat, but I still think this is a > fair proposal: > > 1. It’s not a very outlandish thing.
No, of course it isn't. That doesn't mean we should add it, either. Note: I'm not predisposed against these particular algorithms; not at all. At the same time, I want to be sure we understand why each algorithm we add is being added, and where the limits are. > We already have min/max. Adding a function for the mean would probably > be too much. Collection is a bit of a special API; it should be > reasonably comprehensive to allow developers to keep working at the > most abstract level possible, but you’re right, of course, that there > must be limits. > > 2. Many complex collections will probably decide to cache their > min/max indexes and invalidate them on insertion/removal. Many? I've never heard of a general purpose data structure that did this, (other than sorted collections, which sort of need to do it by definition, in order to produce startIndex and endIndex). > With this API, we could grab those indexes from a stored property; > without it, we’d have to get the min/max elements (which internally > will probably just look up those cached indexes) and work backwards to > find the indexes. Only in generic code that doesn't know it's handling this particular collection. The concrete collection is free to expose whatever it wants to. > I’d rather remove min() and max() and replace them with > collection[collection.indexOfMaxElement]. That is certainly an interesting direction to consider. One might say that no standard library algorithm should ever return an element of the collection unless it is being removed; instead we should always and only return an index to the element. > As far as naming goes, you’re right. “minIndex" and “maxIndex" are far > too similar to “startIndex" and “endIndex”. > > Karl > >> on Sat Apr 16 2016, Nate Cook<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 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 and 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: >> > >> > 1 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 >> > } >> Just with regard to naming, I don't think these work. I read “minIndex” >> as “the minimum index,” and since we expect all indices to be >> comparable, that clearly implies c.minIndex() == c.startIndex. I think >> you'd need “c.indexOfMin()” >> >> I am also really reluctant to add specialized algorithms for things >> that can be trivially composed out of existing parts, e.g. >> >> c.indices.min { c[$0]<c[$1] } >> >> Once we start down this road, we very quickly end up with mapValues, >> mapKeys, indexOfMinimumKey, etc. >> >> -- >> Dave >> >> >> >> > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org > https://lists.swift.org/mailman/listinfo/swift-evolution -- Dave _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution