Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!border1.nntp.ams1.giganews.com!nntp.giganews.com!bcyclone02.am1.xlned.com!bcyclone02.am1.xlned.com!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
References: <9ceklad15llnv3npejq9iuh91soci8aeqo@4ax.com>
Date: Mon, 18 May 2015 21:42:11 +0200
Subject: Re: Slices time complexity
From: Todd <toddrjen@gmail.com>
To: python-list@python.org
Content-Type: multipart/alternative; boundary=f46d04343942d7d28a0516606300
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.113.1431978594.17265.python-list@python.org>
Lines: 103
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:90810

--f46d04343942d7d28a0516606300
Content-Type: text/plain; charset=UTF-8

On May 18, 2015 9:26 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.
>
> From the above link it seems slices work in linear time on all cases.
> And this really has a big impact on certain operations. For instance,
> the code below may surprise some people when they realize it doesn't
> run in linear time on 3.4:
>
>     def minimum(values):
>         if len(values) == 1:
>             return values[0]
>         else:
>             m = minimum(values[1:])
>             return m if m < values[0] else values[0]
>
> 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?

In this case you are copying the items (or rather pointers to the items)
from the list to a new list. This is inherently a O(k) operation.

There are other ways to implement it. I recall the was talk of a way to get
views of sequences, although this would involve keeping the original list
in memory and any changes to the new list would be passed to the original
(this is how numpy works) . It is also possible to do copy-on-write, which
avoids altering the original list but has the same memory problems while
still involving a O(k) copy operation if you want to change the list, and
it is more complex to implement (this is how MATLAB works) .

But to have a new list that can be edited independently requires coping
something, and that will be a O(k) operation, unless you use a radically
different data structure with its own limitations.

--f46d04343942d7d28a0516606300
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<p dir=3D"ltr"><br>
On May 18, 2015 9:26 PM, &quot;Mario Figueiredo&quot; &lt;<a href=3D"mailto=
:marfig@gmail.com">marfig@gmail.com</a>&gt; wrote:<br>
&gt;<br>
&gt; I&#39;d like to understand what I&#39;m being told about slices in<br>
&gt; <a href=3D"https://wiki.python.org/moin/TimeComplexity">https://wiki.p=
ython.org/moin/TimeComplexity</a><br>
&gt;<br>
&gt; Particularly, what&#39;s a &#39;del slice&#39; and a &#39;set slice=
9; and whether this<br>
&gt; information pertains to both CPython 2.7 and 3.4.<br>
&gt;<br>
&gt; From the above link it seems slices work in linear time on all cases.<=
br>
&gt; And this really has a big impact on certain operations. For instance,<=
br>
&gt; the code below may surprise some people when they realize it doesn&#39=
;t<br>
&gt; run in linear time on 3.4:<br>
&gt;<br>
&gt; =C2=A0 =C2=A0 def minimum(values):<br>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 if len(values) =3D=3D 1:<br>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 return values[0]<br>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 else:<br>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 m =3D minimum(values[1:])<br=
>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 return m if m &lt; values[0]=
 else values[0]<br>
&gt;<br>
&gt; Other languages implement slices. I&#39;m currently being faced with a=
 Go<br>
&gt; snippet that mirrors the exact code above and it does run in linear<br=
>
&gt; time.<br>
&gt;<br>
&gt; Is there any reason why Python 3.4 implementation of slices cannot be<=
br>
&gt; a near constant operation?</p>
<p dir=3D"ltr">In this case you are copying the items (or rather pointers t=
o the items) from the list to a new list. This is inherently a O(k) operati=
on. </p>
<p dir=3D"ltr">There are other ways to implement it. I recall the was talk =
of a way to get views of sequences, although this would involve keeping the=
 original list in memory and any changes to the new list would be passed to=
 the original (this is how numpy works) . It is also possible to do copy-on=
-write, which avoids altering the original list but has the same memory pro=
blems while still involving a O(k) copy operation if you want to change the=
 list, and it is more complex to implement (this is how MATLAB works) . </p=
>
<p dir=3D"ltr">But to have a new list that can be edited independently requ=
ires coping something, and that will be a O(k) operation, unless you use a =
radically different data structure with its own limitations. </p>

--f46d04343942d7d28a0516606300--