Efficient way to break up a list into two pieces
showell30 at yahoo.com
Sun Feb 21 22:40:41 CET 2010
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 and
> change the length of l1 (which I store somewhere else). No copying of
> 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:
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:
In particular, look at list_resize(), list_slice(), and
More information about the Python-list