[Tutor] Dictionary

[Magnus Lycka]

At 19:14 2002-11-24 -0800, Danny Yoo wrote:
>However, if we really do want to have a sort of dictionary that does
>return its keys() in sorted order, we may want to use something like a
>"red-black" tree data structure.
>
>A red-black tree behaves similarly to a dictionary --- it maps keys to
>values --- but also makes it convenient to march through the keys and
>values in sorted order, without having to do that intermediate sort()
>step.  Someone's written an implementation in Python:
>
>     http://newcenturycomputers.net/projects/rbtree.html

BTW, the book this code is based on also has a description
of hash tables etc that might be useful to understand the
issues surrounding dictionaries etc. See
http://epaperpress.com/sortsearch/index.html

I'm curious: Has anyone here used and/or benchmarked this Red/Black
tree algorithm. It's all implemented in Python, and I assume that
it should be much slower than the C implementation it copies. Is it
ever faster than a normal python dictionary that is sorted when
needed?

See also http://www.nightmare.com/squirl/python-ext/avl/



-- 
Magnus Lycka, Thinkware AB
Alvans vag 99, SE-907 50 UMEA, SWEDEN
phone: int+46 70 582 80 65, fax: int+46 70 612 80 65
http://www.thinkware.se/  mailto:magnus@thinkware.se