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:
[snip..]
> 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
though.

Thanks

Fuzzyman
http://www.voidspace.org.uk/python/index.shtml

> 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