<div class="gmail_quote">On Sat, Feb 20, 2010 at 6:55 PM, marwie <span dir="ltr"><<a href="mailto:marwie@gmx.de">marwie@gmx.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Now my question is<br>
if there's a similar thing for breaking a list into two parts. Let's<br>
say I want to remove from l1 everything from and including position 10<br>
and store it in l2. Then I can write<br>
<br>
    l2 = l1[10:]<br>
    del l1[10:]</blockquote><div><br>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.<br>
<br>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.<br>
<br>You'd use it something like this:<br><br>>>> from blist import blist<br>>>> l1 = blist()<br>>>> # Here, populate l1 as you normally would<br>>>> l2 = l1[10:]<br>>>> del l1[10:]<br>
<br>It's available at: <a href="http://pypi.python.org/pypi/blist/">http://pypi.python.org/pypi/blist/</a><br></div></div><div style="margin: 2em 0pt;" name="sig_2341e11ee1">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</div><br>