[Python-3000] ordered dict for p3k collections? (original) (raw)

Mark Summerfield 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 sort. 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 versions.

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 languages.

-- Mark Summerfield, Qtrac Ltd., www.qtrac.eu

More information about the Python-3000 mailing list