Is numeric keys of Python's dictionary automatically sorted?

[John]

I am coding a radix sort in python and I think that Python's dictionary may
be a choice for bucket.

The only problem is that dictionary is a mapping without order. But I just
found that if the keys are numeric, the keys themselves are ordered in the
dictionary.

part of my code is like this:
radix={}
for i in range(256):
radix[i]=[]

I checked and found that it is ordered like: {1:[], 2:[], 3[],...}

So I can just print out the contents of the dictionary in the desired order
without additional code.
I also tried adding new numeric keys and found that the dictionary's keys
are still ordered.

However, I am not sure whether it is always like this. Can anybody confirm
my finding?

[Ant]

On Mar 7, 8:18 pm, "John" <[e-mail]:
....

However, I am not sure whether it is always like this. Can anybody confirm
my finding?

>From the standard library docs:

"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

i.e. the behaviour you have discovered is an implementation detail,
and could change in future versions.

[John]

Then is there anyway to sort the numeric keys and avoid future implemetation
confusion?
"Ant" <an****@gmail.comwrote in message
news:11**********************@t69g2000cwt.googlegr oups.com...

On Mar 7, 8:18 pm, "John" <[e-mail]:
...

>However, I am not sure whether it is always like this. Can anybody
confirm
my finding?

>>From the standard library docs:

"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

i.e. the behaviour you have discovered is an implementation detail,
and could change in future versions.

[Carsten Haese]

On Wed, 2007-03-07 at 15:18 -0500, John wrote:

I am coding a radix sort in python and I think that Python's dictionary may
be a choice for bucket.

The only problem is that dictionary is a mapping without order. But I just
found that if the keys are numeric, the keys themselves are ordered in the
dictionary.

No.

The sequence of keys in a dictionary is a coincidental side effect of
the particular Python implementation, the number of keys, the values of
the keys, and the order in which the keys are inserted. You must not
rely on the keys appearing in any particular order.

Here is a simple counterexample that breaks the ordering, at least for
the version I'm running:

>>d = {}
for i in range(0,6): d[10**i] = []

....

>>d

{100000: [], 1: [], 100: [], 1000: [], 10: [], 10000: []}

-Carsten

[Robert Kern]

John wrote:

Then is there anyway to sort the numeric keys and avoid future implemetation
confusion?

sorted(mydict.keys())

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

[Nick Vatamaniuc]

On Mar 7, 3:49 pm, "John" <[e-mail]:

Then is there anyway to sort the numeric keys and avoid future implemetation
confusion?

"Ant" <[e-mail] in message

news:11**********************@t69g2000cwt.googlegr oups.com...

On Mar 7, 8:18 pm, "John" <[e-mail]:
...

However, I am not sure whether it is always like this. Can anybody
confirm
my finding?

>From the standard library docs:

"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

i.e. the behaviour you have discovered is an implementation detail,
and could change in future versions.

I would consider that a bad choice. In the dictionary the keys are a
set i.e. you might as well get a set() when you do d.keys() but the
set() came later so you just get a list. The problem with a list is
that somehow people want to make sense of it's order, just like in
this case. So if instead of asking, he could have just written the
application based on the fact that the keys will always be sorted in
some way. But then one day his application maybe run a different
platform and all of the sudden the keys are not sorted as before and
then disaster strikes.

I hope that dictionary.keys() would return a set to emphasize that
keys are unordered.

You suggested to just set a sort order and keep it consistent, but the
problem is that then you _have to_ maintain the sort order in addition
to the regular dictionary implementation (now it might just be a
byproduct), that is extra work that will have to be done on every
single insertion or deletion just for that rare use case where someone
will want the keys to be sorted.

[Steven D'Aprano]

On Wed, 07 Mar 2007 23:34:20 -0800, Nick Vatamaniuc wrote:

>>From the standard library docs:

"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

i.e. the behaviour you have discovered is an implementation detail,
and could change in future versions.

I would consider that a bad choice. In the dictionary the keys are a
set i.e. you might as well get a set() when you do d.keys() but the
set() came later so you just get a list.

The internal implementation of dictionaries are irrelevant.

Whether the keys "inside" a dictionary are "a set of keys" or "a list of
keys" or "a bunch of keys" is just semantics.

The problem with a list is
that somehow people want to make sense of it's order, just like in
this case.

And the problem with a dictionary is that some people want to make sense
of its order, just like in this case, and the fifty thousand previous
times people have asked this newsgroup how they can sort a dictionary.

So if instead of asking, he could have just written the
application based on the fact that the keys will always be sorted in
some way. But then one day his application maybe run a different
platform and all of the sudden the keys are not sorted as before and
then disaster strikes.

That would be his problem for being a bad coder, not our problem or the
language's fault.

There is no limit to the "could haves" that lead to disaster. Somebody
"could have" assumed that list.sort() returns the sorted list. Somebody
"could have" assumed that "is" is merely a synonym for "==".

And you know something? We get people making those mistakes all the time.
When people make those mistakes, it is *their responsibility*, for being
stupid or not reading the docs or not doing sufficient testing, or simply
for being inexperienced.

I hope that dictionary.keys() would return a set to emphasize that
keys are unordered.

What makes you think that people will magically intuit that sets are
unordered when they insist on thinking that dicts are ordered?

The below-average coder does this:

>>D = {1: None, 2: None, 3:None}
D

{1: None, 2: None, 3: None}

and concludes that dictionaries are ordered. If they are better-than
average, they might try this:

>>D = {1: None, 4: None, 3:None} # keys out of order
D

{1: None, 3: None, 4: None}

Still ordered, right? It's actually quite hard to get a dict with purely
integer keys out of order. So they ASS_U_ME that dicts are ordered.

What makes you think they won't do the same with sets?

>>set((1, 2, 3))

set([1, 2, 3])

>>set((1, 4, 3))

set([1, 3, 4])

>>D = {4: None, 2: None, 1: None, 3: None}
set(D.keys())

set([1, 2, 3, 4])

Sure looks ordered to me.

The solution is:

(1) Don't assume unordered data structures like sets and dicts are
ordered, even if they look like it. They aren't.

(2) If you want the keys of a dict sorted, get the keys, and sort them
when and as you need them.

(3) If you think you want a sorted dictionary, chances are you actually
want a different algorithm.

(4) But if you really do need a sorted dictionary, there are recipes on
the web. Google is your friend. But remember, they will be slower than
regular dictionaries.
--
Steven D'Aprano

[Duncan Booth]

Carsten Haese <ca*****@uniqsys.comwrote:

Here is a simple counterexample that breaks the ordering, at least for
the version I'm running:

>>>d = {}
for i in range(0,6): d[10**i] = []

...

>>>d

{100000: [], 1: [], 100: [], 1000: [], 10: [], 10000: []}

Here's another counterexample which shows that even dictionaries with
the same consecutively numbered small integer keys can vary the order in
which the keys are returned:

>>d1 = dict.fromkeys([1,2])
d2 = dict.fromkeys([9,1,2])
del d2[9]
d1

{1: None, 2: None}

>>d2

{2: None, 1: None}

In current C-Python implementations, the hash code for an integer is
simply the integer itself. That means there is a strong tendency for
consecutive integers to be stored in consecutive slots in the
dictionary. However as soon as you get gaps, or add the keys out of
order, there is a opportunity for higher valued keys to displace lower
valued keys into a different slot.

If you want the keys sorted then sort them.

[Duncan Booth]

Steven D'Aprano <st***@REMOVEME.cybersource.com.auwrote:

If they are better-than
average, they might try this:

>>>D = {1: None, 4: None, 3:None} # keys out of order
D

{1: None, 3: None, 4: None}

Still ordered, right? It's actually quite hard to get a dict with purely
integer keys out of order.

It isn't hard at all.

The next step would be to try something with a few more than 3 keys and
decide that you can't be bothered with all that typing and inventing
values.

dict.fromkeys([randint(0,99) for i in range(10)])

gives you keys out of order about 99.92% of the time.

[Paul Rubin]

"John" <rd*****@sh163.netwrites:

I am coding a radix sort in python and I think that Python's dictionary may
be a choice for bucket.

Why are you coding a radix sort?

The only problem is that dictionary is a mapping without order. But
I just found that if the keys are numeric, the keys themselves are
ordered in the dictionary.

Just an accident, dicts are implemented using hashing, and small
integers hash to themselves.

[Matthias Julius]

"John" <rd*****@sh163.netwrites:

I am coding a radix sort in python and I think that Python's dictionary may
be a choice for bucket.

The only problem is that dictionary is a mapping without order. But I just
found that if the keys are numeric, the keys themselves are ordered in the
dictionary.

part of my code is like this:
radix={}
for i in range(256):
radix[i]=[]

I wonder why nobody has suggested the use of a list:

redix = [[] for i in range(256)]

Matthias

[Ant]

On Mar 8, 8:20 am, Steven D'Aprano <[e-mail]>
wrote:
....

And the problem with a dictionary is that some people want to make sense
of its order, just like in this case, and the fifty thousand previous
times people have asked this newsgroup how they can sort a dictionary.

....

What makes you think they won't do the same with sets?

....

(1) Don't assume unordered data structures like sets and dicts are
ordered, even if they look like it. They aren't.

(2) If you want the keys of a dict sorted, get the keys, and sort them
when and as you need them.

All good points. Is this misconception really as common as you suggest
(obviously there aren't really going to be 50,000 previous threads of
this nature - but you know what I mean). Because if they are, it is
perhaps a case for adding optimized sorted_dict and sorted_set to the
collections module, similar to the TreeSet and TreeMap classes in
Java.