Why are there no ordered dictionaries?
Fuzzyman
fuzzyman at gmail.com
Tue Nov 22 04:20:05 EST 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