On Fri, Jun 26, 2009 at 1:54 AM, Miles Kaufmann <mile...@umich.edu> wrote:
> On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote: > >> That's pretty much the bisect module in a nutshell. It manipulates a >> sorted list using binary search. >> > > With O(n) insertions and removals, though. A decent self-balancing binary > tree will generally do those in O(log n). FWIW, you can get O(log**2 n) inserts and deletes by using the bisect module on my blist extension type (http://pypi.python.org/pypi/blist/). It's a drop-in replacement for list(), with different asymptotic performance characteristics. Copying a blist is O(1), so the functional-programming types can wrap it in non-mutating semantics if they so choose. ;) -- Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-- http://mail.python.org/mailman/listinfo/python-list
