Slices time complexity

[Mark Lawrence]

On 18/05/2015 22:04, Mario Figueiredo wrote:
> 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.
>

Not directly affecting slices but the idea of views has come into Python 
3, please see:-

https://www.python.org/dev/peps/pep-3118/

https://docs.python.org/3/whatsnew/3.3.html#pep-3118-new-memoryview-implementation-and-buffer-protocol-documentation

https://docs.python.org/3/library/stdtypes.html#typememoryview

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence