[Python-3000] ordered dict for p3k collections?
mark at qtrac.eu
Wed Sep 26 13:33:57 CEST 2007
On 2007-09-26, skip at pobox.com wrote:
> Mark> I have put a new version (incorporating another implementation
> Mark> idea from Paul Hankin) on PyPI:
> Mark> http://pypi.python.org/pypi/sorteddict
> From that:
> The main benefit of sorteddicts is that you never have to explicitly
> Surely there must be something more than that. Wrapping sorted() around a
> keys() or values() call is a pretty trivial operation. I didn't see that
> the implementation saved anything.
Assuming you have a good sorteddict implementation (i.e., based on a
balanced tree or a skiplist, not the one I've put up which is just
showing the API) you can gain significant performance benefits.
For example, if you have a large dataset that you need to traverse quite
frequently in sorted order, calling sorted() each time will be expensive
compared to simply traversing an intrinsically sorted data structure.
When I program in C++/Qt I use QMap (a sorteddict) very often; the STL
equivalent is called map. Both the Qt and STL libraries have dict
equivalents (QHash and unordered_map), but my impression is that the
sorted data structures are used far more frequently than the unsorted
If you primarily program in Python, using dict + sorted() is very
natural because they are built into the language. But using a sorted
data structure and never sorting is a very common practice in other
Mark Summerfield, Qtrac Ltd., www.qtrac.eu
More information about the Python-3000