Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: Slices time complexity
Date: Mon, 18 May 2015 19:04:32 -0400
References: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com> <mailman.114.1431978628.17265.python-list@python.org> <19kkla9krk0auuivanhh39lfc8i1csf2ja@4ax.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
In-Reply-To: <19kkla9krk0auuivanhh39lfc8i1csf2ja@4ax.com>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.119.1431990283.17265.python-list@python.org>
Lines: 39
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:90819

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