Slices time complexity

[Bartc]

"Steven D'Aprano" <steve+comp.lang.python at pearwood.info> wrote in message
news:555b0621$0$2753$c3e8da3$76491128 at news.astraweb.com...
> On Tuesday 19 May 2015 05:23, Mario Figueiredo wrote:

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

But sometimes you want an algorithm that works perfectly well in one
language to work just as well in another. (Subject to understood factors,
eg, one language is implemented as native code, another byte-code.)

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

I'm surprised about the slice thing too; I was getting used to the idea of
Python only passing around references, even to small integer values, and now
here it goes and does a copy!

But apparently only a shallow (top-level) copy. Still, it sounds expensive
if you just want to pass part of a list to a function, not the whole thing,
a function which is not going to write into the list (like the OP's
example).

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

Or you could just have a different kind of slice that is just a 'view'.
(Python is a big language to which almost everything else has been bolted
on, so why not?)

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

I agree with the OP, the way slices work in Python is confusing to those who
expect them to work like array assignments. So if B is a million-element
list, then A=B does not copy a million elements, neither shallow or deep.

But A=B[1:] copies 999999 shallow elements. (Pointers I expect, and might
need to change the reference counts of those 999999 elements. And when that
slice is discarded after perhaps a handful of accesses, it might need to
change them all back. if that is the case, then a 'view' kind of slice would
have been better, with an explicit copy operation if needed.)

-- 
Bartc