Slices time complexity

[Oscar Benjamin]

On 20 May 2015 at 10:56, Bartc <bartc at freeuk.com> wrote:
>
> However, I was so impressed with how (C)Python does things (working
> exclusively with pointers, doing assignments by simply copying pointers, and
> using reference counting to manage memory), that I'm experimenting with
> letting my language work the same way. (Also then I can benchmark the two
> more fairly.)
>
> Then I get a little disillusioned when I find out in this thread that a
> simple slice of an array actually copies every element!

It's not an array, it's a list. Lists are often used in Python where
arrays would be used in other languages but they are not the same as
arrays in many other languages since they are not of homogeneous type.
Python has an array module but AIUI it's not used very much. Certainly
whenever I would have a use for the array module I would use numpy's
ndarray instead.

Slicing a list does not copy every element. It copies the references
to each element. The slice creates a new list (of references) rather
than referencing the original but otherwise it is a shallow copy.

> Since I currently
> create a view (a good term I'd never come across before) for a slice, does
> that mean I now also have to do what Python does?

No, creating a view is just fine if that's what you want in your
language. In CPython I use numpy's ndarray for which slices create
views. Sometimes one behaviour is useful and sometimes the other. In
practice I rarely find that list slicing is a performance bottleneck
for anything.


--
Oscar