Slices time complexity

[Mario Figueiredo]

On Mon, 18 May 2015 13:49:45 -0600, Ian Kelly <ian.g.kelly at gmail.com>
wrote:

>> Other languages implement slices. I'm currently being faced with a Go
>> snippet that mirrors the exact code above and it does run in linear
>> time.
>>
>> Is there any reason why Python 3.4 implementation of slices cannot be
>> a near constant operation?
>
>The semantics are different. IIRC, a slice in Go is just a view of
>some underlying array; if you change the array (or some other slice of
>it), the change will be reflected in the slice. A slice of a list in
>Python, OTOH, constructs a completely independent list.
>
>It may be possible that lists in CPython could be made to share their
>internal arrays with other lists on a copy-on-write basis, which could
>allow slicing to be O(1) as long as neither list is modified while the
>array is being shared. I expect this would be a substantial piece of
>work, and I don't know if it's something that anybody has looked into.

This is what I was after. Thank you Ian.

So we basically don't have a view of a list. Makes sense now, since
slice does create a new list. I should have seen that. Thank you once
again.

It would a good addition though. Even if only on specialized
implementations like pypy. Inspecting and not changing lists is a good
chunk of our code. But that's besides the point. I was more interested
in understanding the behavior. Thank you once again.