Efficient way to break up a list into two pieces

[Steve Howell]

On Feb 20, 5:55 pm, marwie <mar... at gmx.de> wrote:
> On 21 Feb., 02:30, Steven D'Aprano <st... at REMOVE-THIS-
>
> cybersource.com.au> wrote:
> > Python lists are arrays of pointers to objects, so copying a slice is
> > fast: it doesn't have to copy the objects, just pointers. Deleting from
> > the end of the list is also quick, because you don't have to move memory,
> > just clear some pointers and change the length field.
>
> > Splitting such an array without copying data is, essentially, impossible.
> > Python lists aren't linked lists.
>
> Well, to split a C array I would simply set l2 to point to l1[10] and
> then
> change the length of l1 (which I store somewhere else). No copying of
> elements
> needed. I would have assumed that python can do something like this
> with its
> internal arrays of pointers, too.
>

When you remove 10 elements off of a list of size 1000, none of the
objects themselves are moved, but the pointers to the objects are all
moved, so k*990 bytes get moved backward, where k is the size of a
pointer (4 or 8 typically on modern computers).

There is no mechanism to advance a pointer forward when you delete or
pop from the top.

I proposed the following patch to implement an advance-the-pointer
scheme, but it is unlikely to be accepted in the near future:

    http://bugs.python.org/file16034/no_mem_penalty.diff

    http://bugs.python.org/issue7784

You can find alternative data structures that might serve your needs
better, such as collections.deque.

If you are interested in how Python lists work internally, you mostly
want to look at listobject.c:

  http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup

In particular, look at list_resize(), list_slice(), and
list_ass_slice().