Efficient way to break up a list into two pieces
daniel at stutzbachenterprises.com
Sun Feb 21 05:18:57 CET 2010
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...
More information about the Python-list