Path: csiph.com!usenet.pasdenom.info!gegeweb.org!newsfeed0.kamp.net!newsfeed.kamp.net!feeder1.cambriumusenet.nl!feed.tweaknews.nl!194.109.133.83.MISMATCH!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
References: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 18 May 2015 13:49:45 -0600
Subject: Re: Slices time complexity
To: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.114.1431978628.17265.python-list@python.org>
Lines: 36
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:90811

On Mon, May 18, 2015 at 1:23 PM, Mario Figueiredo <marfig@gmail.com> wrote:
> I'd like to understand what I'm being told about slices in
> https://wiki.python.org/moin/TimeComplexity
>
> Particularly, what's a 'del slice' and a 'set slice' and whether this
> information pertains to both CPython 2.7 and 3.4.

"Del Slice" is the operation where a slice of a list is deleted, and
"Set Slice" is the operation where a slice is replaced. E.g.:

>>> x = list(range(100))
>>> del x[2:98]
>>> x
[0, 1, 98, 99]
>>> x[1:3] = [7, 6, 5, 4, 3]
>>> x
[0, 7, 6, 5, 4, 3, 99]


> 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.