Slices time complexity

[Todd]

On May 18, 2015 9:26 PM, "Mario Figueiredo" <marfig at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20150518/6d30fa63/attachment.html>