Why are there no ordered dictionaries?

Fuzzyman fuzzyman at gmail.com
Tue Nov 22 10:20:05 CET 2005

Christoph Zwerschke wrote:
> Fredrik Lundh wrote:
> You're right; I found creating a Larosa/Foord OrderedDict in this
> example to be even 8 times slower than an ordinary dict. However, two
> things need to be said here: 1) The dictionary in my exmaple was pretty
> small (only 3 items), so you are not really measuring the performance of
> the ordered dict, but mainly the overhead of using a user derived class
> in comparison with the built-in dict type. And 2) the implementation by
> Larosa/Foord is very slow and can be easily improved, for instance like
> that:
> def __init__(self, init_val = ()):
>      dict.__init__(self, init_val)
>      self.sequence = [x[0] for x in init_val]

But that doesn't allow you to create an ordered dict from another
ordered dict.

It also allows duplicates in the sequence attribute. It's a useful idea



> With this change, creating the ordered dictionary is considerably faster
> and for an average size dictionary, the factor of 8 pretty quickly
> converges against 1.
> But of course, it will always be slower since it is constructed on top
> of the built-in dict. In end effect, you always have to maintain a
> sequence *plus* a dictionary, which will be always slower than a sheer
> dictionary. The ordered dictionary class just hides this uglyness of
> having to maintain a dictionary plus a sequence, so it's rather an issue
> of convenience in writing and reading programs than a performance issue.
> It may be different if the ordered dict would be implemented directly as
> an ordered hash table in C.
> -- Christoph

More information about the Python-list mailing list