> On Dec 29, 2015, at 7:30 AM, Sergey Bolshedvorsky <[email protected]>
> 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 <[email protected]
>> <mailto:[email protected]>> wrote:
>>
>> On Mon, Dec 28, 2015 at 10:29 PM, Sergey Bolshedvorsky via swift-evolution
>> <[email protected] <mailto:[email protected]>> 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 <[email protected]
>> <mailto:[email protected]>>*/
>
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
