Efficient way to break up a list into two pieces

[Daniel Stutzbach]

On Sat, Feb 20, 2010 at 6:55 PM, marwie <marwie at gmx.de> wrote:

> Now my question is
> if there's a similar thing for breaking a list into two parts. Let's
> say I want to remove from l1 everything from and including position 10
> and store it in l2. Then I can write
>
>    l2 = l1[10:]
>    del l1[10:]


With Python's list implementation, there's no faster way to split a list
into two parts.  Because Python lists are essentially variable-length
arrays, Python has to copy O(n) references to create l2 and then decrement
O(n) references to remove them from l1.

I wrote an extension type called the blist to handle this and other
problems.  You use it just like you'd use a list, but it has different
performance characteristics.  It uses a hybrid array-tree structure and
performs copy-on-write behind the scenes, so it takes only O(log n) time to
create l2 and only O(log n) time to trim l1.

You'd use it something like this:

>>> from blist import blist
>>> l1 = blist()
>>> # Here, populate l1 as you normally would
>>> l2 = l1[10:]
>>> del l1[10:]

It's available at: http://pypi.python.org/pypi/blist/
--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100220/b2210bdb/attachment-0001.html>