Why are there no ordered dictionaries?

65 views
Skip to first unread message

Christoph Zwerschke

unread,
Nov 20, 2005, 7:47:05 AM11/20/05
to
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.lang.python/msg/e652d2f771a49857

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

-- Christoph

Ben Finney

unread,
Nov 20, 2005, 8:15:19 AM11/20/05
to
Christoph Zwerschke <ci...@online.de> wrote:
> 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?

What answers have you received that have not been satisfactory?

Some possible answers: The native dict is very fast, partly because
the implementation doesn't need to ensure any particular ordering.
Ordering the keys isn't the normal case, and can be done easily when
needed.

You asked "why not" rather than "has anyone done this anyway"; if
you asked the latter of the Python Cookbook, you might find something
like this:

<URL:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747>

A little old, and pre-dates subclassable native types, but quite
serviceable.

> 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.

In what cases do you find yourself needing a dict that preserves its
key order? Can you present a use case that would be improved by an
ordered dict?

> I fully agree with the following posting where somebody complains
> why so very basic and useful things are not part of the standard
> library:

For my part, I consider it a virtue of Python that the standard
library doesn't change rapidly. It allows many competing
implementations to be shaken out before everyone starts depending on
any one of them.

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

Where to find an answer:

<URL:http://www.python.org/peps/pep-0000.html>

Where to change that answer:

<URL:http://www.python.org/peps/pep-0001.html>

--
\ "One of the most important things you learn from the internet |
`\ is that there is no 'them' out there. It's just an awful lot of |
_o__) 'us'." -- Douglas Adams |
Ben Finney

przemek drochomirecki

unread,
Nov 20, 2005, 8:22:15 AM11/20/05
to

Uzytkownik "Christoph Zwerschke" <ci...@online.de> napisal w wiadomosci
news:dlpr88$ts6$1...@online.de...

i am not sure what is the purpose of having ordered dictionaries built in
python, could u provide any examples?

i use a contruction:
for x in sorted(d.keys())

cheers,

przemek


bon...@gmail.com

unread,
Nov 20, 2005, 8:33:16 AM11/20/05
to

przemek drochomirecki wrote:
> i am not sure what is the purpose of having ordered dictionaries built in
> python, could u provide any examples?
>
> i use a contruction:
> for x in sorted(d.keys())
>
By ordered dict, one usually wants order that is arbitary which cannot
be derived from the content, say insertion order(most ordered dict I
saw use this order).

I am writing a web applications(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting etc.), like this :

d = {'a':{...}, 'b':{....}}

This dict would be passed to the Kid template system which would lay it
out into a HTML form. For quick and dirty forms, I don't want to code
each field individually in the HTML template but just from top to
bottom(or left to right for a table) with a for loop.

However, I still want to group certain fields together. This is my need
of an ordered dict. Or course, I can pass a list along with the dict
and loop over the list and retrieve value from the dict, but that would
mean another things to pass along. And given the constraint of Kid
where everything must be one-liner(expression, no block of code), it
makes thing a bit harder.

Fredrik Lundh

unread,
Nov 20, 2005, 8:58:00 AM11/20/05
to pytho...@python.org
bon...@gmail.com wrote:

> I am writing a web applications(simple forms) which has a number of
> fields. Each field naturally has a name and a number of
> attributes(formatting etc.), like this :
>
> d = {'a':{...}, 'b':{....}}
>
> This dict would be passed to the Kid template system which would lay it
> out into a HTML form. For quick and dirty forms, I don't want to code
> each field individually in the HTML template but just from top to
> bottom(or left to right for a table) with a for loop.
>
> However, I still want to group certain fields together. This is my need
> of an ordered dict.

huh? if you want a list, use a list.

d = [('a', {...}), ('b', {....})]

</F>

bon...@gmail.com

unread,
Nov 20, 2005, 9:11:53 AM11/20/05
to
Didn't I say that for quick and dirty form(usually first draft), I want
a list ? But the same template, it would(may) be further enhanced by
graphic designers in which case, I need direct access to the field
names, thus the dict property.

In this way, I don't have to change the python code just because I
change the presentation in the template.

Nicola Larosa

unread,
Nov 20, 2005, 10:07:42 AM11/20/05
to
> You asked "why not" rather than "has anyone done this anyway"; if
> you asked the latter of the Python Cookbook, you might find something
> like this:
>
> <URL:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747>
>
> A little old, and pre-dates subclassable native types, but quite
> serviceable.

Here's a more recent and tested one, by yours truly (and Michael Foord):

An Ordered Dictionary
http://www.voidspace.org.uk/python/odict.html

--
Nicola Larosa - nico...@m-tekNico.net

How wonderful the world would be if his behaviour and attitude was the
default among rich people - using his money with a vision to improve the
world, instead of getting 8 sportcars and a larger penis.
-- barkholt on Slashdot, October 2005, referring to Mark Shuttleworth

Christoph Zwerschke

unread,
Nov 20, 2005, 4:03:34 PM11/20/05
to
> What answers have you received that have not been satisfactory?

I googled a little bit and haven't found many answers at all. Some were
in the posting I mentioned: Stuff should go into the standard lib only
when it is mature and "right" enough. However, we are already at Python
2.4 and there is still no ordered dictionary, though there is a lot of
other specialized stuff.

> Some possible answers: The native dict is very fast, partly because
> the implementation doesn't need to ensure any particular ordering.

Ok, but that's not an argument against providing ordered dictionaries as
well.

> Ordering the keys isn't the normal case, and can be done easily when
> needed.

That depends. Maybe I do not want the keys to be sorted alphabetically,
but according to some criteria which cannot be derived from the keys
themselves.

> You asked "why not" rather than "has anyone done this anyway"; if
> you asked the latter of the Python Cookbook, you might find something

> like this.

Yes, I also found that others have done it more than once, and I know
that it's not so difficult to do. There are at least two recipes in the
mentioned cookbook and there is odict in pythonutils. The question was
why is it not available in the *standard* lib.

> In what cases do you find yourself needing a dict that preserves its
> key order? Can you present a use case that would be improved by an
> ordered dict?

There are too many different situations and it would be too much to
explain them here, usually in the case mentioned above where the keys
are not sorted alphabetically. I often solve them by using two data
structures, a list or tuple, plus a dictionary. For instance, the list
could contain the names of database fields which shall be output in a
certain order, and the dictionary values could contain human readable
description of the database fields for headers or something. Instead of
maintaining both data structures I feel it would be more natural to use
only one ordered dictionary.

> For my part, I consider it a virtue of Python that the standard
> library doesn't change rapidly. It allows many competing
> implementations to be shaken out before everyone starts depending on
> any one of them.

Ok, but this can be used as an argument to not add anything to the
standard lib any more. There are already enough competing
implementations. Also, the implementation details are not so important,
there must be only agreement on the interface and behavior which should
not be so difficult in this case.

I simply wanted to ask why it is not available in the standard lib,
since I simply don't know

- has it not been demanded loud enough?
- is it really not needed (if you need it it shows you are doing
something wrong)?
- because nobody presented a satisfying implementation yet?
- are there hidden difficulties or controversial issues?

-- Christoph

Christoph Zwerschke

unread,
Nov 20, 2005, 4:19:55 PM11/20/05
to
bon...@gmail.com schrieb:

> By ordered dict, one usually wants order that is arbitary which cannot
> be derived from the content, say insertion order(most ordered dict I
> saw use this order).
> I am writing a web applications(simple forms) which has a number of
> fields. Each field naturally has a name and a number of
> attributes(formatting etc.), like this :
> d = {'a':{...}, 'b':{....}}

Things like that are also my typical use case. The keys usually contain
things like database fields or html form fields, the values contain the
corresponding description, formatting, data type or data itself etc.

The example above is a bit misleading, because using 'a', 'b' as keys
can give the impression that you just have to sort() the keys to have
what you want. So let's make it more realistic:

d = { 'pid': ('Employee ID', 'int'),
'name': ('Employee name', 'varchar'),
'sal': ('Salary', 'float') }

Now if I want these things to be presented in this order, I need to run
through a separate list ('pid', 'name', 'sal') that holds the order.

Ok, you could simply use a list instead of a dictionary:

d = ( ('pid', 'Employee ID', 'int'),
('name', 'Employee name', 'varchar'),
('sal', 'Salary', 'float') )

This works as long as you *only* have to go through the list
sequentially. But maybe you want to print the name with its description
at some other place as well. Now how do you access its description
'Employee name' so easily?

-- Christoph

Ben Finney

unread,
Nov 20, 2005, 4:34:17 PM11/20/05
to
[restored my attribution line so we know who said what]

Christoph Zwerschke <ci...@online.de> wrote:


> Ben Finney wrote:
> > In what cases do you find yourself needing a dict that preserves
> > its key order? Can you present a use case that would be improved
> > by an ordered dict?
>
> There are too many different situations and it would be too much to
> explain them here, usually in the case mentioned above where the
> keys are not sorted alphabetically.

Without an example, it's hard to know what you want to do and whether
an ordered dictionary is the best way to do it.

> > For my part, I consider it a virtue of Python that the standard
> > library doesn't change rapidly. It allows many competing
> > implementations to be shaken out before everyone starts depending
> > on any one of them.
>
> Ok, but this can be used as an argument to not add anything to the
> standard lib any more.

I hope not. Rather, it's an argument not to add something to the
standard library until it's proven (to the BDFL's criteria) that it's
better in than out.

> There are already enough competing
> implementations.

Have they been sufficiently shaken out to show a clearly superior
version? Is any version sufficiently beneficial to write a PEP for its
inclusion in the standard library?

> I simply wanted to ask why it is not available in the standard lib,
> since I simply don't know
>
> - has it not been demanded loud enough?

Loud demands don't count for much. PEPs with popular working
implementations do.

> - is it really not needed (if you need it it shows you are doing
> something wrong)?

You dismissed a request for your use cases with handwaving. How can we
know?

> - because nobody presented a satisfying implementation yet?

I'm not sure what you mean by "satisfying".

> - are there hidden difficulties or controversial issues?

Another possibility: ordered dictionaries are not needed when Python
2.4 has the 'sorted' builtin.

--
\ "Those who will not reason, are bigots, those who cannot, are |
`\ fools, and those who dare not, are slaves." -- "Lord" George |
_o__) Gordon Noel Byron |
Ben Finney

Fredrik Lundh

unread,
Nov 20, 2005, 4:45:22 PM11/20/05
to pytho...@python.org
Christoph Zwerschke wrote:

> The example above is a bit misleading, because using 'a', 'b' as keys
> can give the impression that you just have to sort() the keys to have
> what you want. So let's make it more realistic:
>
> d = { 'pid': ('Employee ID', 'int'),
> 'name': ('Employee name', 'varchar'),
> 'sal': ('Salary', 'float') }
>
> Now if I want these things to be presented in this order, I need to run
> through a separate list ('pid', 'name', 'sal') that holds the order.
>
> Ok, you could simply use a list instead of a dictionary:
>
> d = ( ('pid', 'Employee ID', 'int'),
> ('name', 'Employee name', 'varchar'),
> ('sal', 'Salary', 'float') )

if you restructure the list somewhat

d = (
('pid', ('Employee ID', 'int')),
('name', ('Employee name', 'varchar')),
('sal', ('Salary', 'float'))
)

you can still loop over the list

for key, (name, type) in d:
print key, name, type # e.g. generate form entry

> This works as long as you *only* have to go through the list
> sequentially. But maybe you want to print the name with its description
> at some other place as well. Now how do you access its description
> 'Employee name' so easily?

but you can easily generate an index when you need it:

index = dict(d)

name, type = index["pid"]
print name

the index should take less than a microsecond to create, and since it
points to the members of the original dict, it doesn't use much memory
either...

</F>

bon...@gmail.com

unread,
Nov 20, 2005, 7:09:35 PM11/20/05
to

Fredrik Lundh wrote:
> but you can easily generate an index when you need it:
>
> index = dict(d)
>
> name, type = index["pid"]
> print name
>
> the index should take less than a microsecond to create, and since it
> points to the members of the original dict, it doesn't use much memory
> either...
>
Using the same logic, we don't need types other than string in a DBMS
as we can always convert a string field into some other types when it
is needed.

Of course there are more than one way to skin a cat(well it may be
against the general idiom of python) but in some situation certain way
is preferred.

Christoph Zwerschke

unread,
Nov 20, 2005, 7:27:22 PM11/20/05
to
Fredrik Lundh wrote:
> if you restructure the list somewhat
> d = (
> ('pid', ('Employee ID', 'int')),
> ('name', ('Employee name', 'varchar')),
> ('sal', ('Salary', 'float'))
> )
> you can still loop over the list
> ...

> but you can easily generate an index when you need it:
> index = dict(d)

That's exactly the kind of things I find myself doing too often and what
I was talking about: You are using *two* pretty redundant data
structures, a dictionary and a list/tuple to describe the same thing.
Ok, you can use a trick to automatically create the dictionary from the
tuple, but still it feels somewhat "unnatural" for me. A "ordered
dictionary" would be the more "natural" data structure here.

I also wanted to mention the uglyness in the definition (nested tuples),
but then I understood that even an ordered dictionary would not
eliminate that uglyness, since the curly braces are part of the Python
syntax and cannot be used for creating ordered dictionaries anyway. I
would have to define the ordered dictionary in the very same ugly way:

d = odict(('pid', ('Employee ID', 'int')),


('name', ('Employee name', 'varchar')),
('sal', ('Salary', 'float')))

(Unless the Python syntax would be extend to use double curly braces or
something for ordered dictionaries - but I understand that this is not
an option.)

-- Christoph

bon...@gmail.com

unread,
Nov 20, 2005, 7:45:23 PM11/20/05
to

Ben Finney wrote:
> Another possibility: ordered dictionaries are not needed when Python
> 2.4 has the 'sorted' builtin.
>
What does sorted() have anythng to do with orders like insertion order,
or some arbitary order that instead of a,b,c,d,e, I want it as e, c, b,
d, a ?

Personally, I have needs for ordered dict but I don't think it should
be in standard library though, as different situation called for
different behaviour for "ordered" and skewing my code to a standard lib
way is no good.

What I think is better is like the itertools recipe of giving example
of how one can make their own based on the needs.

Christoph Zwerschke

unread,
Nov 20, 2005, 8:02:36 PM11/20/05
to
Ben Finney wrote:

> Without an example, it's hard to know what you want to do and whether
> an ordered dictionary is the best way to do it.

I have indicated an example, discussed in more detail in another subthread.

>> There are already enough competing implementations.
> Have they been sufficiently shaken out to show a clearly superior
> version? Is any version sufficiently beneficial to write a PEP for its
> inclusion in the standard library?

At least it shows I'm not the only one who thinks ordered dictionaries
may be sometimes nice to have.

>> I simply wanted to ask why it is not available in the standard lib,
>> since I simply don't know
>> - has it not been demanded loud enough?
> Loud demands don't count for much. PEPs with popular working
> implementations do.

Sorry, I did not mean "loud enough" but "often enough". The same what
you are calling "popular."

>> - because nobody presented a satisfying implementation yet?
> I'm not sure what you mean by "satisfying".

You can take your own definition: "sufficiently shaken out", "working",
"popular", and "succifiently beneficial" and "proven (to the BDFL's
criteria)".

> Another possibility: ordered dictionaries are not needed when Python
> 2.4 has the 'sorted' builtin.

The 'sorted' function does not help in the case I have indicated, where

"I do not want the keys to be sorted alphabetically, but according to
some criteria which cannot be derived from the keys themselves."

-- Christoph

Christoph Zwerschke

unread,
Nov 20, 2005, 8:32:46 PM11/20/05
to
bon...@gmail.com wrote:
> Personally, I have needs for ordered dict but I don't think it should
> be in standard library though, as different situation called for
> different behaviour for "ordered" and skewing my code to a standard lib
> way is no good.

I have started the thread in the first place because I believed it is
pretty unabmiguous what an "ordered dictionary" is and how it should
behave. That's why I asked myself why something that straigthforward has
not been added to the standard lib yet. Maybe I'm wrong; I must admit
that I haven't meditated about it very much.

Do you have an example for different options of behavior?

-- Christoph

bon...@gmail.com

unread,
Nov 20, 2005, 8:42:13 PM11/20/05
to
As mentioned, most ordered dict I saw is "insertion order" based. I
assume that is the need of their creators. But that is not my need, so
there are at least two behaviour. What I need is a "preferred order".
Say if I have designed a web form(correspond to a database table), I
just want say 3 fields that goes before anything else in the
presentation. The rest I don't care as the DBA may create more fields
later which I don't want to then update my code yet again.

Alex Martelli

unread,
Nov 20, 2005, 9:09:47 PM11/20/05
to
Christoph Zwerschke <ci...@online.de> wrote:
...

> I have started the thread in the first place because I believed it is
> pretty unabmiguous what an "ordered dictionary" is and how it should

I think you're wrong here. People in the past who have requested or
implemented stuff they called 'ordered dicts' in the past had in mind
drastically different things, based on some combination of insertion
orders, keys, and _values_. So, ambiguity is definitely present in the
phrase 'ordered dictionary', because there are so many different
criteria whereby the 'ordering' could take place.

Note the plural in 'insertion orderS': some people care about the FIRST
time a key was added to a dict, some about the LAST time it was added,
some about the latest time it was 'first inserted' (added and wasn't
already there) as long as it's never been deleted since that occasion --
and these are just a few of the multifarious orders based on the time of
insertions and deletions of keys. The number of variations is
staggering, e.g., consider

x['a'] = 1
x['b'] = 2
x['a'] = 1

in some applications you'd want to have 'b' come before 'a' because the
last time of addition was earlier for 'b' -- but in others you might
want 'a' first because the latest addition wasn't really one, since it
didn't really change anything (because the value inserted was the same
as the one already there -- it would be different, for those other apps,
if the RHS of the third assignment was 0 rather than 1...).

To get 'ordered dicts' into Python, you have to identify ONE unambiguous
definition which has a large-enough number of use-cases, possibly
customizable through some reasonably SIMPLE combination of flags and a
callable or two, like the 'sorted' built-in has a 'reversed' flag and
'key' and 'cmp' optional callables. Expect a lot of flak from those who
have been pining for an 'ordered dict' which does NOT match your one
unambiguous definition...;-)

If the field of use cases for 'ordered dicts' is just too fragmented,
it's quite possible that it's best not to have any single kind built-in,
even though, could all different use cases be combined (which by
hypothesis is unfeasible), "critical mass" would be reached...


Alex

Alex Martelli

unread,
Nov 20, 2005, 9:09:47 PM11/20/05
to
bon...@gmail.com <bon...@gmail.com> wrote:
...

> there are at least two behaviour. What I need is a "preferred order".
> Say if I have designed a web form(correspond to a database table), I
> just want say 3 fields that goes before anything else in the
> presentation. The rest I don't care as the DBA may create more fields
> later which I don't want to then update my code yet again.

preferred_fields = ['foo', 'bar', 'baz']

def process_preferred_fields():
global preferred_fields
temp = {}
for i, field in enumerate(preferred_fields):
temp[field] = '%s%s' % (chr(0), chr(i))
preferred_fields = temp
process_preferred_fields()
del process_preferred_fields

def sort_key(akey, preferred_fields=preferred_fields):
return preferred_fields.get(akey, akey)
del preferred_fields

## ...build dictionary d...

# now output d...:
for k in sorted(d, key=sort_key):
print k, d[k]

Season to taste if you want non-preferred fields emitted other than
alphabetically, or if you want to wrap this stuff into a class, etc.
(Note: untested code, so typos &c are quite possible). This assumes
that no 'real' key is a non-string, and no 'real' key starts with
chr(0), but it's quite easy to tweak for slightly different specs (at
worst by defining a custom type designed to always compare less than any
real key, and wrapping the preferred_fields entry in instances of that
custom type... having such instances compare with each other based on
the index within preferred_fields of the key they're wrapping, etc etc).


Alex

Alex Martelli

unread,
Nov 20, 2005, 9:11:00 PM11/20/05
to
Christoph Zwerschke <ci...@online.de> wrote:
...
> The 'sorted' function does not help in the case I have indicated, where
> "I do not want the keys to be sorted alphabetically, but according to
> some criteria which cannot be derived from the keys themselves."

Ah, but WHAT 'some criteria'? There's the rub! First insertion, last
insertion, last insertion that wasn't subsequently deleted, last
insertion that didn't change the corresponding value, or...???


Alex

Mike Meyer

unread,
Nov 20, 2005, 9:12:03 PM11/20/05
to
Christoph Zwerschke <ci...@online.de> writes:

> Ben Finney wrote:
>> Another possibility: ordered dictionaries are not needed when Python
>> 2.4 has the 'sorted' builtin.
> The 'sorted' function does not help in the case I have indicated,
> where "I do not want the keys to be sorted alphabetically, but
> according to some criteria which cannot be derived from the keys
> themselves."

And how would an ordered dictionary help in this case?

<mike
--
Mike Meyer <m...@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.

bon...@gmail.com

unread,
Nov 20, 2005, 9:23:44 PM11/20/05
to
Thanks. For me, I don't need such complex thing, it is just like :

d = somedict_from_db()
prefer=['f','a',b']

def my_order(d):
for x in prefer:
if x in d: yield x
s = frozenset(prefer)
for x in d:
if x not in s: yield x

Peter Hansen

unread,
Nov 20, 2005, 9:40:19 PM11/20/05
to
bon...@gmail.com wrote:
> Using the same logic, we don't need types other than string in a DBMS
> as we can always convert a string field into some other types when it
> is needed.

You mean, like SQLite does? (http://www.sqlite.org/datatypes.html)

-Peter

bon...@gmail.com

unread,
Nov 20, 2005, 9:48:09 PM11/20/05
to
Yup, they are using similar logic.

Bengt Richter

unread,
Nov 20, 2005, 11:53:54 PM11/20/05
to
On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke <ci...@online.de> wrote:
>> Ordering the keys isn't the normal case, and can be done easily when
>> needed.
>
>That depends. Maybe I do not want the keys to be sorted alphabetically,
>but according to some criteria which cannot be derived from the keys
>themselves.
You mean involving also the values? What's wrong with
sorted(plaindict.items(), key=your_ordering_function) ?

>>> def show(*a): print a
...
>>> sorted(dict((c,ord(c)) for c in 'abcd').items(), key=show)
(('a', 97),)
(('c', 99),)
(('b', 98),)
(('d', 100),)
[('a', 97), ('c', 99), ('b', 98), ('d', 100)]

What key function would you like, to generate the value that is actually used
to define the ordering?

>>> sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[0])
[('a', 97), ('b', 98), ('c', 99), ('d', 100)]
>>> sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[1])
[('a', 97), ('b', 98), ('c', 99), ('d', 100)]
>>> sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:-t[1])
[('d', 100), ('c', 99), ('b', 98), ('a', 97)]
>>> sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[1]&1)
[('b', 98), ('d', 100), ('a', 97), ('c', 99)]
>>> sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,t[1]))
[('b', 98), ('d', 100), ('a', 97), ('c', 99)]
>>> sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,-t[1]))
[('d', 100), ('b', 98), ('c', 99), ('a', 97)]
And being able to reverse the end result is handy
>>> sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,-t[1]), reverse=True)
[('a', 97), ('c', 99), ('b', 98), ('d', 100)]

You may need to upgrade your Python though ;-)

Regards,
Bengt Richter

bon...@gmail.com

unread,
Nov 21, 2005, 12:12:52 AM11/21/05
to

Bengt Richter wrote:
> On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke <ci...@online.de> wrote:
> >> Ordering the keys isn't the normal case, and can be done easily when
> >> needed.
> >
> >That depends. Maybe I do not want the keys to be sorted alphabetically,
> >but according to some criteria which cannot be derived from the keys
> >themselves.
> You mean involving also the values? What's wrong with
> sorted(plaindict.items(), key=your_ordering_function) ?
>
Not according to the content of the data, not just the "key". Or in
other words, some other metadata that is not present in the data. A
typical thing, like order of creation. Or some arbitary order. For
example :

I present a data grid/table in a HTML form and the user just drag and
drop and rearrange the columns order.

Of course, you may say, just put another column that represent
this(some reporting programs I have seen do it this way) and that is an
option but not the only option.

Ben Finney

unread,
Nov 21, 2005, 12:34:39 AM11/21/05
to
bon...@gmail.com <bon...@gmail.com> wrote:
> [sort by] some other metadata that is not present in the data.
> [...]

> Of course, you may say, just put another column that represent
> this(some reporting programs I have seen do it this way) and that is
> an option but not the only option.

It's a pretty good option, and very commonly used. It's known as the
"Schwartzian transform", or more descriptively, the "Decorate, Sort,
Undecorate" pattern.

<URL:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234>

--
\ "Experience is that marvelous thing that enables you to |
`\ recognize a mistake when you make it again." -- Franklin P. |
_o__) Jones |
Ben Finney

bon...@gmail.com

unread,
Nov 21, 2005, 12:42:53 AM11/21/05
to

Ben Finney wrote:
> bon...@gmail.com <bon...@gmail.com> wrote:
> > [sort by] some other metadata that is not present in the data.
> > [...]
> > Of course, you may say, just put another column that represent
> > this(some reporting programs I have seen do it this way) and that is
> > an option but not the only option.
>
> It's a pretty good option, and very commonly used. It's known as the
> "Schwartzian transform", or more descriptively, the "Decorate, Sort,
> Undecorate" pattern.
>
Whether it is a good option is judged by the person implement it as he
is the one seeing the whole thing, and not some snippet(or concept) on
the usenet.

Fredrik Lundh

unread,
Nov 21, 2005, 2:50:20 AM11/21/05
to pytho...@python.org
bon...@gmail.com wrote:

> Fredrik Lundh wrote:
> > but you can easily generate an index when you need it:
> >
> > index = dict(d)
> >
> > name, type = index["pid"]
> > print name
> >
> > the index should take less than a microsecond to create, and since it
> > points to the members of the original dict, it doesn't use much memory
> > either...
> >
> Using the same logic, we don't need types other than string in a DBMS
> as we can always convert a string field into some other types when it
> is needed.

No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
There's no parsing involved, nor any type guessing. And given the use case,
it's more than fast enough, and doesn't copy any data.

If you think that's the same thing as parsing strings, you've completely missed
the point.

</F>

bon...@gmail.com

unread,
Nov 21, 2005, 3:05:33 AM11/21/05
to

Well, forget about the missing/not missing the point.

My point is, there are various of reasons why we need different data
types in an RDBMS, just the same as why we need list, dict. There is
nothing stop me from using a list as dict(just scan it till I find it),
why would I I create a dict(your new view of the same data) ? Coding
convenience, speed or whatever.

If I need the dict feature 90% of the time, and the list feature 10% of
the time. I want an ordered dict. Rather than a list and create this
new view every time and every where I want to use it as a dict.

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

Fredrik Lundh

unread,
Nov 21, 2005, 4:12:29 AM11/21/05
to pytho...@python.org
bon...@gmail.com wrote:

> If I need the dict feature 90% of the time, and the list feature 10% of
> the time.

Wasn't your use case that you wanted to specify form fields in
a given order (LIST), render a default view of the form in that
order (LIST), and, later on, access the field specifiers in an
arbitrary order, based on their key (DICT). Sure looks like it's
the LIST aspect that's important here...

("but assume that I have some other use case" isn't a valid use
case)

> I want an ordered dict. Rather than a list and create this new view every
> time and every where I want to use it as a dict.

You want an ordered dict because you say you want one, not be-
cause it's the best way to address your use case. That's fine, but
it's not really related to the question asked in the subject line.

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

Copying the entire data structure hardly qualifies as "creating a
new view". dict() doesn't do that; in this use case, it doesn't cost
you anything to use it.

Everything has a cost in Python. Things aren't free just because
they're implemented by some other module.

But when things are free, they're often a good choice.

</F>

bon...@gmail.com

unread,
Nov 21, 2005, 4:54:38 AM11/21/05
to

Fredrik Lundh wrote:
> bon...@gmail.com wrote:
>
> > If I need the dict feature 90% of the time, and the list feature 10% of
> > the time.
>
> Wasn't your use case that you wanted to specify form fields in
> a given order (LIST), render a default view of the form in that
> order (LIST), and, later on, access the field specifiers in an
> arbitrary order, based on their key (DICT). Sure looks like it's
> the LIST aspect that's important here...
Yes. But whether LIST aspect or DICT is important is well, opinion. So
let's leave it there.

>
> > I want an ordered dict. Rather than a list and create this new view every
> > time and every where I want to use it as a dict.
>
> You want an ordered dict because you say you want one, not be-
> cause it's the best way to address your use case. That's fine, but
> it's not really related to the question asked in the subject line.
Again, best way is decided by ME. If I am entering a coding contest
which is organized by YOU, that is a different story. As for related to
the subject line, since when I said my preference or use case has
anything to do with the subject line ? I have said in another post that
I don't think there should be one in the standard library, which is
directly about the subject line.

>
> > parsing or not parsing is not the point, and parsing/converting is
> > still "create a new view" of an existing data structure.
>
> Copying the entire data structure hardly qualifies as "creating a
> new view". dict() doesn't do that; in this use case, it doesn't cost
> you anything to use it.

doesn't cost me anything ? That is good news to me.

Antoon Pardon

unread,
Nov 21, 2005, 5:04:26 AM11/21/05
to
Op 2005-11-21, Christoph Zwerschke schreef <ci...@online.de>:

> bon...@gmail.com wrote:
>> Personally, I have needs for ordered dict but I don't think it should
>> be in standard library though, as different situation called for
>> different behaviour for "ordered" and skewing my code to a standard lib
>> way is no good.
>
> I have started the thread in the first place because I believed it is
> pretty unabmiguous what an "ordered dictionary" is and how it should
> behave. That's why I asked myself why something that straigthforward has
> not been added to the standard lib yet. Maybe I'm wrong; I must admit
> that I haven't meditated about it very much.

Well it doesn't seem that obvious, because the two recipes you have
gotten, do something different from what I understand as an ordered
dictionary.

The two recipes order the keys by insertion order.

My idea would have been that some order was defined
on your keys in advance and that when you iterated over
the dictionary, the results would be ordered in sequence
of key order.

> Do you have an example for different options of behavior?

Well you have two above. Maybe someone can think of something
else.

Which behaviour are you looking for?

--
Antoon Pardon

Ben Sizer

unread,
Nov 21, 2005, 5:55:04 AM11/21/05
to
Fredrik Lundh wrote:
> bon...@gmail.com wrote:
> > Using the same logic, we don't need types other than string in a DBMS
> > as we can always convert a string field into some other types when it
> > is needed.
>
> No, that's not the same logic. The dict() in my example doesn't convert be-
> tween data types; it provides a new way to view an existing data structure.

This is interesting; I would have thought that the tuple is read and a
dictionary created by inserting each pair sequentially. Is this not the
case?

--
Ben Sizer

Fredrik Lundh

unread,
Nov 21, 2005, 6:55:18 AM11/21/05
to pytho...@python.org
Ben Sizer wrote:

> > No, that's not the same logic. The dict() in my example doesn't convert be-
> > tween data types; it provides a new way to view an existing data structure.
>
> This is interesting; I would have thought that the tuple is read and a
> dictionary created by inserting each pair sequentially. Is this not the
> case?

pointers to the members of each pair, yes. but a pointer copy is a
cheap operation (for the given use case, we're only talking about a
few dozen pairs anyway, at the most).

this is a common fallacy; Python programmers underestimate the
cost of adding extra layers to their code (e.g. by using an ordered
dict data structure that has to incrementally update both a list and
a dictionary), and overestimate the cost of letting the C layer do
bulk operations.

(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...)

</F>

Fuzzyman

unread,
Nov 21, 2005, 10:01:16 AM11/21/05
to

Fredrik Lundh wrote:
> Ben Sizer wrote:
>
> > > No, that's not the same logic. The dict() in my example doesn't convert be-
> > > tween data types; it provides a new way to view an existing data structure.
> >
> > This is interesting; I would have thought that the tuple is read and a
> > dictionary created by inserting each pair sequentially. Is this not the
> > case?
>
[snip..]

> (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...)
>

So, so long as you want to use the dictionary less than six times -
it's faster to store/access it as a list of tuples. ;-)

Everytime you want to access (or assign to) the data structure as a
dictionary, you have to re-create the index.

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

> </F>

Alex Martelli

unread,
Nov 21, 2005, 10:44:28 AM11/21/05
to
bon...@gmail.com <bon...@gmail.com> wrote:
...

> d = somedict_from_db()
> prefer=['f','a',b']
>
> def my_order(d):
> for x in prefer:
> if x in d: yield x
> s = frozenset(prefer)
> for x in d:
> if x not in s: yield x

Yes, a much cleaner architecture (if you don't need any sorting on
non-preferred keys of d) than the ponderous general one I proposed. A
'key' approach with this behavior would be:

def my_key(k):
try: return prefer.index(k)
except ValueError: return len(prefer)

Now, 'for x in sorted(d, key=my_key)' should be equivalent to 'for x in
my_order(d)' thanks to the stability of sorting when the 'key' callable
returns equal values.

Neither of these way-simpler approaches is (I suspect) optimal for
speed, in the unlikely event one cares about that. The idea of
preprocessing the 'preferred' list once and for all outside of the
function (which I used heavily in my previous post) might yield some
speed-up, for example:

def my_key_fast(k, _aux=dict((k,i) for i,k in enumerate(prefer),
_l=len(prefer)):
return _aux.get(k, _l)

It's very unlikely that this situation warrants such optimization, of
course, I'm just "thinking aloud" about abstract possibilities.


Alex

Christoph Zwerschke

unread,
Nov 21, 2005, 11:54:18 AM11/21/05
to
Ben Finney wrote:

>>> Another possibility: ordered dictionaries are not needed when Python
>>> 2.4 has the 'sorted' builtin.

Christoph Zwerschke wrote:

>> The 'sorted' function does not help in the case I have indicated,
>> where "I do not want the keys to be sorted alphabetically, but
>> according to some criteria which cannot be derived from the keys
>> themselves."

Mike Meyer wrote:

> And how would an ordered dictionary help in this case?

Maybe there is some confusion between an "orderable" and an "ordered"
dictionary. When I talk about "ordered dictionary", then in the simplest
case I just set up my ordered dictionary with my preferred key order and
it stays like that. This allows me to later iterate through the
dictionary in this preferred order, while being still able to randomly
access data from the dictionary at other places.

-- Christoph

Alex Martelli

unread,
Nov 21, 2005, 11:58:40 AM11/21/05
to
Fredrik Lundh <fre...@pythonware.com> wrote:
...
> ("but assume that I have some other use case" isn't a valid use
> case)

+1 QOTW


Alex

Christoph Zwerschke

unread,
Nov 21, 2005, 12:13:57 PM11/21/05
to
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

Christoph Zwerschke

unread,
Nov 21, 2005, 12:29:21 PM11/21/05
to
Alex Martelli wrote:

> Note the plural in 'insertion orderS': some people care about the FIRST
> time a key was added to a dict, some about the LAST time it was added,
> some about the latest time it was 'first inserted' (added and wasn't
> already there) as long as it's never been deleted since that occasion --
> and these are just a few of the multifarious orders based on the time of
> insertions and deletions of keys.

Ok, I start to understand that ambiguity emerges when you delete and
insert items. I didn't think much about this problem because my use
cases usually do not involve inserttion or deletion after the ordered
dictionary has been created.

But I think the following rule is "natural" enough to consider it as THE
standard behavior of ordered dictionaries:

"Insertion: If the key exists: Don't change the order. If it does not
exist: Append it to the sequence of keys. Deletion: Remove from the
sequence of keys."

I think this is also the behavior of associative arrays in PHP or Perl
and could be considered as the "ONE unambiguous definition".

-- Christoph

Aahz

unread,
Nov 21, 2005, 1:04:37 PM11/21/05
to
In article <1h6c6t4.1hc5owk13rgcrhN%al...@mail.comcast.net>,

Alex Martelli <al...@mail.comcast.net> wrote:
>
>I think you're wrong here. People in the past who have requested or
>implemented stuff they called 'ordered dicts' in the past had in mind
>drastically different things, based on some combination of insertion
>orders, keys, and _values_. So, ambiguity is definitely present in the
>phrase 'ordered dictionary', because there are so many different
>criteria whereby the 'ordering' could take place.
>
>Note the plural in 'insertion orderS': some people care about the FIRST
>time a key was added to a dict, some about the LAST time it was added,
>some about the latest time it was 'first inserted' (added and wasn't
>already there) as long as it's never been deleted since that occasion --
>and these are just a few of the multifarious orders based on the time of
>insertions and deletions of keys.

Ayup. In our application, not only do we have ordered dicts, we also
have something called a "sectioned dict", which is a dict-like object
that also looks like a regular class instance with attribute access. The
section part actually has multiple dicts (the sections) which are
layered, so that a dict key in the top layer overrides the value of the
key in lower layers. We traditionally have used it such that the
sections are accessed in MRU orders; last week, we added a new feature
that allows setting section values without changing section order (to
allow setting a default, essentially).
--
Aahz (aa...@pythoncraft.com) <*> http://www.pythoncraft.com/

"If you think it's expensive to hire a professional to do the job, wait
until you hire an amateur." --Red Adair

Tom Anderson

unread,
Nov 21, 2005, 2:02:00 PM11/21/05
to
On Sun, 20 Nov 2005, Alex Martelli wrote:

> Christoph Zwerschke <ci...@online.de> wrote:
>
>> The 'sorted' function does not help in the case I have indicated, where
>> "I do not want the keys to be sorted alphabetically, but according to
>> some criteria which cannot be derived from the keys themselves."
>
> Ah, but WHAT 'some criteria'? There's the rub! First insertion, last
> insertion, last insertion that wasn't subsequently deleted, last
> insertion that didn't change the corresponding value, or...???

All the requests for an ordered dictionary that i've seen on this group,
and all the cases where i've needed on myself, want one which behaves like
a list - order of first insertion, with no memory after deletion. Like the
Larosa-Foord ordered dict.

Incidentally, can we call that the "Larosa-Foord ordered mapping"? Then it
sounds like some kind of rocket science discrete mathematics stuff, which
(a) is cool and (b) will make Perl programmers feel even more inadequate
when faced with the towering intellectual might of Python. Them and their
Scwartzian transform. Bah!

tom

--
Baby got a masterplan. A foolproof masterplan.

Kay Schluehr

unread,
Nov 21, 2005, 2:53:43 PM11/21/05
to
Fredrik Lundh wrote:

> huh? if you want a list, use a list.
>
> d = [('a', {...}), ('b', {....})]

If one wants uniform access to a nested data structure like this one
usually starts writing a wrapper class. I do not think the requirement
is anyhow deeper than a standard wrapper around such a list ( as a
model ) but the implementation may be different with respect to optimal
time complexitiy of element access. But the interface of the wrapper
class of d might resemble that of a dict. While the interface is that
of a dict the implementation is closer to a nested list. An "ordered
dict" would lower the impedance between a dict and a list.

Kay

Fredrik Lundh

unread,
Nov 21, 2005, 10:59:08 AM11/21/05
to pytho...@python.org
"Fuzzyman" wrote:

> [snip..]
> > (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...)
>
> So, so long as you want to use the dictionary less than six times -
> it's faster to store/access it as a list of tuples. ;-)

nope. that's not what I said. I said that you can recreate the index
six times in the time it takes to create a single OrderedDict instance.
if you need to use index more than that, it's not that hard to keep a
reference to it.

> Everytime you want to access (or assign to) the data structure as a
> dictionary, you have to re-create the index.

the use case we're talking about here (field descriptors) doesn't involve
assigning to the data structure, once it's created.

I'll repeat this one last time: for the use cases presented by Zwerschke
and "bonono", using a list as the master data structure, and creating the
dictionary on demand, is a lot faster than using a ready-made ordered
dict implementation. if you will access things via the dictionary a lot,
you can cache the dictionary somewhere. if not, you can recreate it
several times and still get a net win.

for other use cases, things may be different, but nobody has presented
such a use case yet. as I said earlier, "let's assume we have another use
case" is not a valid use case.

</F>

Christoph Zwerschke

unread,
Nov 21, 2005, 5:09:57 PM11/21/05
to
Fredrik Lundh wrote:
> I'll repeat this one last time: for the use cases presented by Zwerschke
> and "bonono", using a list as the master data structure, and creating the
> dictionary on demand, is a lot faster than using a ready-made ordered
> dict implementation. if you will access things via the dictionary a lot,
> you can cache the dictionary somewhere. if not, you can recreate it
> several times and still get a net win.

You're right in pointing out that the advantage of ordered dictionaries
(unless you use an omptimized C implementation) is not a performance gain.

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.

The advantage of using an ordered dictionary is that you can set up your
ordered dictionary (say, describing your database columns) once, and
then can access it in any way you like in the following: Iterate over it
in a guaranteed order or access item, always refering to the same
object, without needing to care about building and caching auxiliary
objects with different names depending on what you are doing.

-- Christoph

Bengt Richter

unread,
Nov 21, 2005, 6:31:59 PM11/21/05
to
On 20 Nov 2005 21:12:52 -0800, "bon...@gmail.com" <bon...@gmail.com> wrote:

>
>Bengt Richter wrote:
>> On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke <ci...@online.de> wrote:
>> >> Ordering the keys isn't the normal case, and can be done easily when
>> >> needed.
>> >
>> >That depends. Maybe I do not want the keys to be sorted alphabetically,
>> >but according to some criteria which cannot be derived from the keys
>> >themselves.
>> You mean involving also the values? What's wrong with
>> sorted(plaindict.items(), key=your_ordering_function) ?
>>
>Not according to the content of the data, not just the "key". Or in
>other words, some other metadata that is not present in the data. A
>typical thing, like order of creation. Or some arbitary order. For
>example :
>
>I present a data grid/table in a HTML form and the user just drag and
>drop and rearrange the columns order.

^^[1]
[1] implies known info of before and after rearrangement. Where do these
come from, and are the two states expressed as ordered sets of keys generated and stored somewhere?
The point is, to re-order, you need a mapping from unordered data dict keys to values which the sorted
builtin function will order in the way you want. (BTW, if you use DSU, make sure the data is not modifying
your sort in an undesired way. Passing a key function to sorted makes it easy to exclude unwanted data from
the sort). If you have data that determines a new ordering of keys, it has to be accessed somehow, so
you just need to make it accessible to a handy helper that will generate your key function. E.g,
with before and after lists of keys expressing e.g. drag-drop before and after orderings, lambda can do the
job of getting you dict items in the new order, e.g., where bef and aft are lists that define the desired orderings
before and after in the sense of sort_precedence = bef.index[key_in_bef] and same for aft.

sorted(thedict.items(),key=lambda t:dict(zip(bef,((k in aft and aft.index(k) or len(aft)+bef.index(k)) for k in bef))[t[0]])

Ok, that one-liner grew a bit ;-)


>
>Of course, you may say, just put another column that represent
>this(some reporting programs I have seen do it this way) and that is an
>option but not the only option.
>

Maybe you could keep the rearranged_keys vector in a per-user cookie, if it's a web app
and amounts to a user personalization?

( posting delayed >12 hrs due to news server prob ;-/ )

Regards,
Bengt Richter

Bengt Richter

unread,
Nov 21, 2005, 6:32:25 PM11/21/05
to
On Mon, 21 Nov 2005 01:27:22 +0100, Christoph Zwerschke <ci...@online.de> wrote:

>Fredrik Lundh wrote:
>> if you restructure the list somewhat
>> d = (
>> ('pid', ('Employee ID', 'int')),
>> ('name', ('Employee name', 'varchar')),
>> ('sal', ('Salary', 'float'))
>> )
>> you can still loop over the list
>> ...


>> but you can easily generate an index when you need it:
>> index = dict(d)
>

>That's exactly the kind of things I find myself doing too often and what
>I was talking about: You are using *two* pretty redundant data
>structures, a dictionary and a list/tuple to describe the same thing.
>Ok, you can use a trick to automatically create the dictionary from the
>tuple, but still it feels somewhat "unnatural" for me. A "ordered
>dictionary" would be the more "natural" data structure here.
>
But, as has been mentioned**n, this is only one example of an ordering one
could make default for an "ordered" dictionary. Suppose you say it should
be ordered by insertion order, so
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"? The devil is always going
to be in the details. Maybe you want a model that works more like a list
of key:value pairs with just optimized access to a pair by key name as
well as position in the list. Or maybe you want to permit append and
NOT prevent [('a',1), ('a':2)] and maybe d['a'] => [1, 2] ???

The point is that Python is a nice lego set, and pre-molded castles
don't re-use well, even if they suit a particular you to a t ;-)

Note that is isn't hard to snap a few pieces together to make an ordered
dict to your own specs. But IMO it belongs in pyPI or such, not in the system
library. At least until it gets a lot of mileage -- and MMV ;-)

>I also wanted to mention the uglyness in the definition (nested tuples),
>but then I understood that even an ordered dictionary would not
>eliminate that uglyness, since the curly braces are part of the Python
>syntax and cannot be used for creating ordered dictionaries anyway. I
>would have to define the ordered dictionary in the very same ugly way:
>
>d = odict(('pid', ('Employee ID', 'int')),
> ('name', ('Employee name', 'varchar')),
> ('sal', ('Salary', 'float')))
>
>(Unless the Python syntax would be extend to use double curly braces or
>something for ordered dictionaries - but I understand that this is not
>an option.)
>
Whatever your odict does, if I had type a lot of definitions for it
I think I would write a QnD helper to make this work:

d = odict(prep("""

pid, Employee ID, int
name, Employee name, varchar # (comments to be ignored)
sal, Salary, float # alignment as above not mandatory
other, Something else, long, additional elements, allowed in second tuple?
"""))

Bengt Richter

unread,
Nov 21, 2005, 6:33:34 PM11/21/05
to
On 21 Nov 2005 01:54:38 -0800, "bon...@gmail.com" <bon...@gmail.com> wrote:

>
>Fredrik Lundh wrote:
>> bon...@gmail.com wrote:
>>
>> > If I need the dict feature 90% of the time, and the list feature 10% of
>> > the time.
>>
>> Wasn't your use case that you wanted to specify form fields in
>> a given order (LIST), render a default view of the form in that
>> order (LIST), and, later on, access the field specifiers in an
>> arbitrary order, based on their key (DICT). Sure looks like it's
>> the LIST aspect that's important here...
>Yes. But whether LIST aspect or DICT is important is well, opinion. So
>let's leave it there.

>>
>> > I want an ordered dict. Rather than a list and create this new view every
>> > time and every where I want to use it as a dict.
>>
>> You want an ordered dict because you say you want one, not be-
>> cause it's the best way to address your use case. That's fine, but
>> it's not really related to the question asked in the subject line.
>Again, best way is decided by ME. If I am entering a coding contest
>which is organized by YOU, that is a different story. As for related to
>the subject line, since when I said my preference or use case has
>anything to do with the subject line ? I have said in another post that
>I don't think there should be one in the standard library, which is
>directly about the subject line.

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 ;-)
Then someone can take less time than many of these posts takes to make a
list subclass that also acts like the dict when you want or a dict subclass that
also acts like a list when you want. Which methods from which would you like
as-is, and which modified? Any additional methods or properties? DYFR ;-)

>
>>
>> > 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.

>> Copying the entire data structure hardly qualifies as "creating a
>> new view". dict() doesn't do that; in this use case, it doesn't cost
>> you anything to use it.
>doesn't cost me anything ? That is good news to me.

Well, if you want something specific, it WILL cost you the effort to DYFR in detail ;-)

Alex Martelli

unread,
Nov 21, 2005, 7:41:37 PM11/21/05
to
Christoph Zwerschke <ci...@online.de> wrote:
...

> But I think the following rule is "natural" enough to consider it as THE
> standard behavior of ordered dictionaries:
>
> "Insertion: If the key exists: Don't change the order. If it does not
> exist: Append it to the sequence of keys. Deletion: Remove from the
> sequence of keys."
>
> I think this is also the behavior of associative arrays in PHP or Perl

Perl hashes now keep track of 'order of keys'? That's new to me, they
sure didn't back when I used Perl! It's been a while, but a little
googling shows me, e.g at
<http://www.openarchives.org/pipermail/oai-implementers/2002-September/0
00642.html>, assertions such as:
"""
Hashes don't maintain key order. To get them in sorted order try:

foreach $i (sort keys(%afiliacao))
"""
which fully match my memories. Could you produce a URL to support the
hypothesis that Perl has changed its behavior? What about PHP? Thanks!

> and could be considered as the "ONE unambiguous definition".

"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 "conceptually compact".

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.

If we ran such an experiment, what fraction do you think would serve to
convince Guido that a dict 'ordered' by your definition is necessary in
Python 2.5's standard library (presumably in module 'collections')?


Alex

Fredrik Lundh

unread,
Nov 22, 2005, 3:20:34 AM11/22/05
to pytho...@python.org
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. The idea of
combining unordered mappings and ordered sequences is older than
Python itself.

</F>

Christoph Zwerschke

unread,
Nov 22, 2005, 3:40:33 AM11/22/05
to
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 "conceptually 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

unread,
Nov 22, 2005, 4:06:07 AM11/22/05
to
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

unread,
Nov 22, 2005, 4:14:41 AM11/22/05
to pytho...@python.org
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

unread,
Nov 22, 2005, 4:20:05 AM11/22/05
to
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

Christoph Zwerschke

unread,
Nov 22, 2005, 4:26:22 AM11/22/05
to
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

unread,
Nov 22, 2005, 4:41:44 AM11/22/05
to
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

unread,
Nov 22, 2005, 5:16:22 AM11/22/05
to

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

unread,
Nov 22, 2005, 5:29:25 AM11/22/05
to
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

unread,
Nov 22, 2005, 5:01:25 AM11/22/05
to
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!

bon...@gmail.com

unread,
Nov 22, 2005, 6:07:47 AM11/22/05