Why are there no ordered dictionaries?

[Christoph Zwerschke]

Fredrik Lundh wrote:
> (as an example, on my machine, using Foord's OrderedDict class
> on Zwerschke's example, creating the dictionary in the first place
> takes 5 times longer than the index approach, and accessing an
> item takes 3 times longer.  you can in fact recreate the index 6
> times before OrderedDict is faster; if you keep the index around,
> the OrderedDict approach never wins...)

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]

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