how to sort a hash list without generating a new object?

Daniel Stutzbach stutzbach at google.com
Wed Aug 3 12:33:17 EDT 2011


On Tue, Aug 2, 2011 at 5:53 PM, Chris Rebert <clp2 at rebertia.com> wrote:

> If you /really/ need a sorted mapping datatype, google for
> "sorteddict" (which is quite distinct from OrderedDict).
> Or look for a binary search tree or skip list implementation of some
> sort; but these aren't commonly used in Python, so it may be hard to
> find a good one.
>

The blist package (I'm the author) provides a list-like type that has O(log
n) insertions and deletions.  It provides a sorteddict type that uses the
blist type under-the-hood.

blist's "sorteddict" supports the "key" parameter (which works like
list.sort's key parameter), which the original poster could use to maintain
the keys in reverse order.

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

There's no overhead to learn how to use the new types.  A blist works
exactly like a list but with different performance characteristics, and a
sorteddict works just like a dict but keeps the keys sorted.

-- 
Daniel Stutzbach
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110803/ee049647/attachment.html>


More information about the Python-list mailing list