> On Dec 29, 2015, at 7:30 AM, Sergey Bolshedvorsky <ser...@bolshedvorsky.com> > wrote: > > Hi Dmitri, > > Thank you for your feedback! I’ve updated a proposal based on your comments: > https://github.com/apple/swift-evolution/pull/77 > <https://github.com/apple/swift-evolution/pull/77> > >> What jumps at me immediately is that the APIs are using integers to specify >> positions in the collection. I think they should be using collection's >> indices instead. > Yes you are right, the APIs should use collection indexes. > >> I'm unsure why we need `first` and `last` -- shouldn't the API operate on >> the whole collection? We have slices to operate on subsequences. > > The C++ implementation allows to rotate all elements of collection or only > some of them. A precondition of this function is that > 0 <= first <= middle <= last < count
This should be handled by slicing and rotating a slice. In-place slice mutation is not yet efficient, but we have an open radar asking for the necessary core language feature to make it so (non-pointer proxy addressors). >> Another point to consider is how the call site of these functions looks like: > > I’ve added 2 API usage examples to PR: > > Example of rotating all elements of the collection: > > let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9] > let rotated = numbers.rotateFrom(0, middle: 3, last: 8) > // rotated contains [4, 5, 6, 7, 8, 9, 1, 2, 3] There should be an in-place rotation algorithm as well, and for both varieties we should have a way of getting back the index of the old start element in the rotated collection. I would start with the in-place algorithms are likely more of a challenge. > Example of rotating some elements of the collection: > > let numbers = [10, 12, 13, 11, 15, 14] > let rotated = numbers.rotateFrom(1, middle: 3, last: 4) > // rotated contains [10, 11, 12, 13, 15, 14] > > >> It is interesting that you are proposing that the new algorithms should >> produce lazy views. I agree this is consistent with the rest of the >> library, but I'm worried about the performance implications. Have you >> thought about this? One point to keep in mind is that you can implement the >> `_copyToNativeArrayBuffer()` and `_initializeTo()` entry points in all new >> lazy collections, using the optimal eager algorithm. This way, converting >> them to arrays will be fast. > Thanks for pointing out the performance issue with lazy views. I will draft > the implementation of algorithms for regular collections at first and then I > will think how it can be reused with lazy views. Err, I don’t think Dmitri pointed anything out; he merely asked you to consider performance. But I must admit that I don’t understand the concern. Many of our eager algorithms for are implemented by copying lazy views to an array. Personally, I would implement a rotate as something like: extension CollectionType { func rotatedAt(midPoint: Index) -> /* Return type */{ let result = c.lazy.flatten([ c[midPoint..<c.endIndex], c[startIndex..<midPoint] ]) // or, for optimization, c.flatten(CollectionOfTwo(c[midPoint..<c.endIndex], c[startIndex..<midPoint] )) return (result, calculateIndexOfMidPoint()) } } calculateIndexOfMidPoint can start out being O(N) if necessary; you should be able to add enough API to the LazyFlattenCollection that you can synthesize the position more efficiently though. > > Sergey > > > >> On 29 Dec 2015, at 06:38, Dmitri Gribenko <griboz...@gmail.com >> <mailto:griboz...@gmail.com>> wrote: >> >> On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution >> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote: >> Hi all, >> >> I have created a PR with with a formal proposal for this feature: >> https://github.com/apple/swift-evolution/pull/77 >> <https://github.com/apple/swift-evolution/pull/77> >> >> What are your thoughts? >> >> Thank you for the proposal! >> >> What jumps at me immediately is that the APIs are using integers to specify >> positions in the collection. I think they should be using collection's >> indices instead. >> >> I'm unsure why we need `first` and `last` -- shouldn't the API operate on >> the whole collection? We have slices to operate on subsequences. >> >> It is interesting that you are proposing that the new algorithms should >> produce lazy views. I agree this is consistent with the rest of the >> library, but I'm worried about the performance implications. Have you >> thought about this? One point to keep in mind is that you can implement the >> `_copyToNativeArrayBuffer()` and `_initializeTo()` entry points in all new >> lazy collections, using the optimal eager algorithm. This way, converting >> them to arrays will be fast. >> >> Another point to consider is how the call site of these functions looks like: >> >> collection.rotate(10, middle: 20, last: 30) >> >> The first number hangs in the air, it is unclear what its meaning is. >> >> Dmitri >> >> -- >> main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if >> (j){printf("%d\n",i);}}} /*Dmitri Gribenko <griboz...@gmail.com >> <mailto:griboz...@gmail.com>>*/ >
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution