Why are there no ordered dictionaries?

[Christoph Zwerschke]

This is probably a FAQ, but I dare to ask it nevertheless since I
haven't found a satisfying answer yet: Why isn't there an "ordered
dictionary" class at least in the standard list? Time and again I am
missing that feature. Maybe there is something wrong with my programming
style, but I rather think it is generally useful.

I fully agree with the following posting where somebody complains why so
very basic and useful things are not part of the standard library:
http://groups.google.com/group/comp....52d2f771a49857

Are there plans to get it into the standard lib sometime?

-- Christoph

[Christoph Zwerschke]

Alex Martelli schrieb:

Perl hashes now keep track of 'order of keys'? That's new to me, they
sure didn't back when I used Perl!
Maybe I shouldn't have talked about Perl when I'm an ignoramus about
that language... You're right, Perl has unordered arrays. That was new
to me since I associate the term "array" always with "ordered" and I
just remembered that PHP's assoc arrays are similar to Perl's but in
fact, and the examples I have read did not mention about that problem.
What about PHP?
You can conclude that PHP's assoc arrays are ordered from the fact that
the language provides a ksort() function to order the keys. And I think
PHP's insertion order is the one I mentioned in my last post.

Anyway, it would be interesting to examine this in detail and how this
is implemented in other languages.
"first insertion (since the last deletion if any)" is ONE unambiguous
definition, but surely not "_the_ ONE" with emphasis on ``the''.
I see nothing _ambiguous_ (nor _unnatural_) in being interested in the
*last* insertion, for example; indeed if phrased as "upon insertion, put
the key at the end of the sequence" (whether it was already elsewhere in
the sequence of not), with no need for conditionals regarding previous
existence, it might appear more "conceptual ly compact".
But it would not satisfy the concept of "keys of a dictionary" which are
always unique.

BTW, there are some boundary conditions that should be fulfilled for the
insertion order, most obviously:

If you define an ordered dict that way:

d = odict()
d['a'] = 1
d['b'] = 2
d['c'] = 3

The keys should then be orderes as ('a', 'b', 'c').
Anyway -- subclassing dict to implement your definition is reasonably
easy, and we could put the resulting package on the Cheese Shop. I hope
python.org keeps good enough statistics to be able to tell us, a couple
months later, how many people downloaded said package, vs how many
people downloaded a complete Python distro; of course, that ratio is
biased (in favour of the package) by the fact that many people already
have a complete distro available, while initially nobody would have the
package, but if we measure when things settle, after letting a month of
two or 'transient' pass, that effect might be lessened.

That would be also biased (in favour of Python) by the fact that
probably very little people would look for and use the package in the
cheese shop if they were looking for ordered dicts. I for example would
probably use ordered dicts if they were part of the standard lib, but
not if I have to install it as an obscure separate package. So I don't
think that will give us a real clue how many people would like ordered
dicts in the standard lib.

But anyway, if I find some time, I will research a little bit more about
the issue and create such a package, because it seems to me that the
existing packages and recipes are not really satisfying and you're right
it seems to be reasonably easy. It's on my todo list now...

-- Christoph

[Christoph Zwerschke]

Bengt Richter schrieb:

Ok, so if not in the standard library, what is the problem? Can't find what
you want with google and PyPI etc.? Or haven't really settled on what your
_requirements_ are? That seems to be the primary problem people who complain
with "why no sprollificator mode?" questions.
What I don't understand is why legitimate questions such as "why are
there no ordered dictionaries" are immediately interpreted as
*complaints* and not just as questions. If I ask such a question, I am
not complaining but trying to simply figure out *why* there is no such
thing. Probably there are reasons and all I want to know is find these
reasons and learn a little bit more about Python in doing so.

Why can't such questions be discussed in a factual, calm and friendly way?
They don't know what they really mean when it comes down to a DYFR
(Define Your Felicitous Requirements) challenge.

I don't think that this was true in this case, and even if this is the
outcome, those who asked the question will have learned something.

I think a discussion group is not there for only presenting mature,
sophisticated thoughts and concepts, but also for "thinking loud"
together with other about these issues. We all know that clarifying our
thoughts works often best if you discuss them with others. And I think
that's one purpose of discussion lists. Asking questions should not be
immediately be discouraged, even silly questions. If it is really a FAQ,
you can simply point to the FAQ or add the answer in the FAQ list if it
is missing there.

-- Chris

[Fredrik Lundh]

Alex Martelli wrote:

What about PHP? Thanks!

according to some random PHP documentation I found on the intarweb:

An array in PHP is actually an ordered map. A map is a type that
maps values to keys.

and later:

A key may be either an integer or a string. If a key is the standard
representation of an integer, it will be interpreted as such (i.e. "8"
will be interpreted as 8, while "08" will be interpreted as "08"). Floats
in key are truncated to integer.

and later:

You cannot use arrays or objects as keys. Doing so will result in a
warning: Illegal offset type.
at which point my brain raised an exception.

</F>

[Fuzzyman]

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__(s elf, 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

[Christoph Zwerschke]

Bengt Richter wrote:

d = OrderedDict(); d[1]='one'; d[2]='two' =>> list(d) => [1, 2]
ok, now we do d[1]='ein' and what is the order? list(d) => [2, 1] ??
Or do replacements not count as "insertions "?
If you simply set a value for a key that already exists, the order
should not be changed. I think this is intuitive.
Or maybe you want to permit append and NOT prevent
[('a',1), ('a':2)] and maybe d['a'] => [1, 2] ???

You could ask the same question about dict. I think that is not an
option. Why should you want odict behave different than dict?

I still believe that the concept of an "ordered dictionary" ("behave
like dict, only keep the order of the keys") is intuitive and doesn't
give you so much scope for ambiguity. But probably I need to work on an
implementation to become more clear about possible hidden subtleties.

-- Christoph

[Kay Schluehr]

Christoph Zwerschke wrote:

That would be also biased (in favour of Python) by the fact that
probably very little people would look for and use the package in the
cheese shop if they were looking for ordered dicts.

Does anyone actually use this site? While the Vaults offered a nice
place and a nice interface the Cheese Shop has the appeal of a code
slum.

Kay

[Fuzzyman]

Kay Schluehr wrote:

Christoph Zwerschke wrote:

That would be also biased (in favour of Python) by the fact that
probably very little people would look for and use the package in the
cheese shop if they were looking for ordered dicts.
Does anyone actually use this site? While the Vaults offered a nice
place and a nice interface the Cheese Shop has the appeal of a code
slum.

Hmmm.. it's *the* repository for Python code. I expect quite a few
people use it...

:-)

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

[Steven D'Aprano]

On Tue, 22 Nov 2005 09:20:34 +0100, Fredrik Lundh wrote:

Tom Anderson wrote:

Incidentally, can we call that the "Larosa-Foord ordered mapping"?

The implementation, sure.

Then it sounds like some kind of rocket science discrete mathematics stuff

But math folks usually name things after the person(s) who came
up with the idea, not just some random implementer.

No no no! In maths things are usually named after Euler, or the first
person to discover them after Euler.
--
Steven.

[Magnus Lycka]

Christoph Zwerschke wrote:

But please see my other reply: If the dictionary has more than 3 items
(say 10 or 20), and an effective ordered dict is used, it's not really
"a lot" slower. At least if we are talking about a situation were "on
demand" is "always". So, on the other side there isn't such a big
performance loss when using ordered dictionaries as well.

There is no performance issue involved with this usecase at all!

It doesn't matter if it's hundreds of tuples of strings in a list
if it's supposed to be presented in a GUI. Recreating a dict from
that is bound to be magnitudes faster than getting the stuff
visible on the screen, at least if we're talking web apps. So is
using a reasonable odict implementation, if that's what you want.

I think the issue is not to overload the already extensive standard
library with trivial things that can easily be replaced by your own
three line wrapper, especially if there are a number of different
semantics that could be imagined for such a thingie.

The C++ std lib has an ordered "dict" class called map, and that's
ordered by key. Others suggested ordering by value, and there are a
number of different interpretations of the 'order by insertion time'
theme in the air. This clearly smells like "fix your own thing and
leave it out of the standard library".

With one of these solutions picked as Python's "ordered dict", we'll
make things slightly more convenient for a few programmers and just
burden others with something that sounds right for them, but turns
out not to solve their problems. Or, we could try to make a bunch
of different solution, increasing the cognitive burden for all who
learn Python while solving non-problems. This just isn't going to
happen!

[bonono]

Bengt Richter wrote:

Ok, so if not in the standard library, what is the problem? Can't find what
you want with google and PyPI etc.? Or haven't really settled on what your
_requirements_ are? That seems to be the primary problem people who complain
with "why no sprollificator mode?" questions. They don't know what they really
mean when it comes down to a DYFR (Define Your Felicitous Requirements) challenge.
So DYFR ;-)

Beat me. I am not the one asking the question.

> parsing or not parsing is not the point, and parsing/converting is
> still "create a new view" of an existing data structure.

So you'd like the mechanics to be automated and hidden? Then you need to
DYFR for using the black box you want. Methods, semantics.

Lose you. don't know what you want to say.