Slices time complexity

[Steven D'Aprano]

On Tuesday 19 May 2015 05:23, Mario Figueiredo 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.


Get a slice: x = mylist[2:15]

Set a slice: mylist[2:15] = [2, 4, 6, 8]

Del a slice: del mylist[2:15]

 
> From the above link it seems slices work in linear time on all cases.

I wouldn't trust that is always the case, e.g. deleting a contiguous slice 
from the end of a list could be O(1).


> 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:

I'm sure that lots of things surprise people who assume that every 
language's performance characteristics are identical.

Python is not Lisp. Lisp is not Java. Java is not Forth. Forth is not Lua. 
Lua is not Fortran. Fortran is not PHP. Do you see a pattern yet? :-)


>     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.

I spot a terminology error here. What Go calls a slice and what Python calls 
a slice are *not the same thing*. A Go slice is a view into an array. Python 
slicing is a *method call* to copy, assign, or delete part of a sequence.

Also, Python slices can accept three arguments, not just two, which may be 
arbitrary objects. Go slices cannot.


> Is there any reason why Python 3.4 implementation of slices cannot be
> a near constant operation?

Yes. (1) Backwards compatibility. (2) That would go against the design of 
Python slices that they are copies. (3) That would upset those who want and 
expect a slice to be a copy.

I'll tell you what -- Python slices have worked this way for over 20 years. 
You should propose to the Go designers that Go is confusing because it 
doesn't match Python's behaviour, and they should change the meaning of 
slices in Go to match Python. There's not as much Go code in the world as 
Python code, so that will be far less disruptive. Tell them that Go should 
be just like Python, otherwise it will confuse users who expect Go slices to 
behave like Python slices.

Do let us know what the Go designers say.



-- 
Steven