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

[Dan Stromberg]

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

> On Tue, Aug 2, 2011 at 11:02 AM, smith jack <thinke365 at gmail.com> wrote:
> > the source code is as follows
> >
> > x={}
> > x['a'] = 11
> > x['c'] = 19
> > x['b'] = 13
> > print x
>
> 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.
>

I've found a need for such a thing a couple of times.

Anyway, here are some other possibilities:

http://stromberg.dnsalias.org/~dstromberg/treap/
http://pypi.python.org/pypi/bintrees/0.3.0

The treap code is considered by its author (me) production-quality, has an
extensive test suite, and is known to work on CPython 2.x, CPython 3.x, PyPy
and Jython.  The CPython's can optionally be sped up with a Cython variant
of the same code (autogenerated from a single source file using m4), and
while I test on all 4 regularly, lately I mostly run it in production using
the pure python version on PyPy.

EG:

$ python
Python 2.6.6 (r266:84292, Sep 15 2010, 15:52:39)
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import treap
>>> t = treap.treap()
>>> import random
>>> for i in xrange(10):
...    t[random.random()] = random.random()
...
>>> print list(t.items())
[(0.049542221325585611, 0.60627903220498502), (0.26787423324282511,
0.95374362416785075), (0.45599886628328978, 0.57612454878587427),
(0.46375501394309371, 0.28130836755784228), (0.54144253493651362,
0.47941229743653202), (0.54584770558330997, 0.49062231291462766),
(0.5592476615748635, 0.39138521009523863), (0.73976131715214732,
0.99783565376628391), (0.7638117918732078, 0.55600393733208187),
(0.88094790991949967, 0.90033960217787801)]
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20110802/1cb63fc0/attachment-0001.html>