<div class="gmail_quote">On Fri, Jun 26, 2009 at 1:54 AM, Miles Kaufmann <span dir="ltr"><<a href="mailto:milesck@umich.edu">milesck@umich.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="im">On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">That's pretty much the bisect module in a nutshell. It manipulates a<br>

sorted list using binary search.<br>
</div></blockquote>
<br>
With O(n) insertions and removals, though.  A decent self-balancing binary tree will generally do those in O(log n).<font color="#888888"></font></blockquote><div><br>FWIW, you can get O(log**2 n) inserts and deletes by using the bisect module on my blist extension type (<a href="http://pypi.python.org/pypi/blist/">http://pypi.python.org/pypi/blist/</a>).  It's a drop-in replacement for list(), with different asymptotic performance characteristics.  <br>
<br>Copying a blist is O(1), so the functional-programming types can wrap it in non-mutating semantics if they so choose. ;)<br></div></div><blockquote style="margin: 1.5em 0pt;">--<br>
Daniel Stutzbach, Ph.D.<br>
President, <a href="http://stutzbachenterprises.com">Stutzbach Enterprises, LLC</a>
</blockquote>