[Tutor] Sorted dictionaries

[Danny Yoo]

On Fri, 25 Jul 2003, Willi Richert wrote:

> > We can implement a "sorted" map using a data structure called a
> > "Red-Black Tree".  Chris Gonnerman has written a nice rbtree module:
> >
> >     http://newcenturycomputers.net/projects/rbtree.html
>
> BTW, which algorithms work behind dict() and sort() ?

Hi Willi,


Python's Dictionary type is based on a classic data structure called a
"hash table".  If you'd like, we can give a small introduction on hash
tables to get a feel for how they work.  I think I wrote something about
it a year or so ago on Python-Tutor, but I'm having a hard time finding
it...

Also, you can always look at Python's source code if you're interested in
the primary literature.  *grin* Seriously though, most of Python's source
code is fairly readable, and it's sorta neat to see how it all the gears
work.  Here's a link to the 'dictobject.c' source:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/python/python/dist/src/Objects/dictobject.c?rev=HEAD&content-type=text/vnd.viewcvs-markup

as well as development notes:

http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/python/python/dist/src/Objects/dictnotes.txt?rev=HEAD&content-type=text/vnd.viewcvs-markup



The sort() method of lists had used an algorithm called 'samplesort' to
minimize the number of comparisons it used.  But around the middle of
2002, Tim Peters thought about sorting a bit:

    http://mail.python.org/pipermail/python-dev/2002-July/026837.html

This thread is actually a lot of fun to read!  The end result was that the
sorting routine that Python uses was completely overhauled, and recent
versions of Python now use "timsort":

    http://pythonowns.blogspot.com/2002_07_28_pythonowns_archive.html


Good luck!