ANN: blist 1.1.1 - now with sortedlist, sortedset, and sorteddict

[Daniel Stutzbach]

blist 1.1.1 is now available:

        http://pypi.python.org/pypi/blist/

What is blist?
--------------

The blist is a drop-in replacement for the Python list the provides
better performance when modifying large lists.  Python's built-in list
is a dynamically-sized array; to insert or removal an item from the
beginning or middle of the list, it has to move most of the list in
memory, i.e., O(n) operations.  The blist uses a flexible, hybrid
array/tree structure and only needs to move a small portion of items
in memory, specifically using O(log n) operations.

For small lists, the blist and the built-in list have virtually
identical performance.

What's new?
-----------

blist 1.1 introduces other data structures based on the blist:

- sortedlist
- sortedset
- weaksortedlist
- weaksorteset
- sorteddict
- btuple

These additional data structures are only available in Python 2.6 or
higher, as they make use of Abstract Base Classes.

The sortedlist is a list that's always sorted.  It's iterable and
indexable like a Python list, but to modify a sortedlist the same
methods you would use on a Python set (add, discard, or remove).

>>> from blist import sortedlist
>>> my_list = sortedlist([3,7,2,1])
>>> my_list
sortedlist([1, 2, 3, 7])
>>> my_list.add(5)
>>> my_list[3]
5
>>>

The sortedlist constructor takes an optional "key" argument, which may
be used to change the sort order just like the sorted() function.

>>> from blist import sortedlist
>>> my_list = sortedlist([3,7,2,1], key=lambda i: -i)
sortedlist([7, 3, 2, 1]
>>>

The sortedset is a set that's always sorted.  It's iterable and
indexable like a Python list, but modified like a set.  Essentially,
it's just like a sortedlist except that duplicates are ignored.

>>> from blist import sortedset
>>> my_set = sortedset([3,7,2,2])
sortedset([2, 3, 7]
>>>

The weaksortedlist and weaksortedset are weakref variations of the
sortedlist and sortedset.

The sorteddict works just like a regular dict, except the keys are
always sorted.  The sorteddict should not be confused with Python
2.7's OrderedDict type, which remembers the insertion order of the
keys.

>>> from blist import sorteddict
>>> my_dict = sorteddict({1: 5, 6: 8, -5: 9})
>>> my_dict.keys()
[-5, 1, 6]
>>>

The btuple is a drop-in replacement for the built-in tuple.  Compared
to the built-in tuple, the btuple offers the following advantages:

- Constructing a btuple from a blist takes O(1) time.
- Taking a slice of a btuple takes O(n) time, where n is the size of
  the original tuple.  The size of the slice does not matter.

>>> from blist import blist, btuple
>>> x = blist([0])             # x is a blist with one element
>>> x *= 2**29                 # x is a blist with > 500 million elements
>>> y = btuple(x)              # y is a btuple with > 500 million elements

Feedback
--------

We're eager to hear about your experiences with the blist.  You can
email me at daniel at stutzbachenterprises.com.  Alternately, bug reports
and feature requests may be reported on our bug tracker at:
http://github.com/DanielStutzbach/blist/issues

--
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/20100131/2e344208/attachment.html>