Slices time complexity

[Terry Reedy]

On 5/18/2015 5:04 PM, Mario Figueiredo 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.

Actually we do if you think about things the right way.  An index can be 
viewed as representing the slice of a list from the indexed item to the 
end.  In this view, "for i in range(len(seq)):" works with progressively 
shrinking slices, the same as with the recursive version of the algorithm.

The analogy is better with iterators.  iter(seq) returns a seq_iterator 
that initially represent a tail slice consisting of the entire sequence. 
  Each next(seq_iter) call return the head of the sequence and mutates 
seq_iter to represent a reduced tail-slice.  The effect is the same as 
repeatedly stripping the head from a linked list. For statements 
automate the next calls and StopIteration checks.

-- 
Terry Jan Reedy