can the sequence of entries in a dictionary be depended on?

[Priya]

Hi,
I'm writing a program where i iterate through the entries in a
dictionary using a for loop. This for-loop is enclosed by another loop
which traverses through a list and checks the relation between each
entry in the list and each entry in the dictionary.
while I know that dictionaries are 'unordered', I'd like to know if
the order of traversal will be the same each time the dictionary is
iterated through.
like if i have
dictionary={key1:"val1", key2:"val2",key3="val3"...}
for i in (1,10)
for value in dictionary1:
print value
am i assured that i always get the same sequence of outputs for any
two values of i?
Thanks.

 

[Diez B. Roggisch]

Hi,
I'm writing a program where i iterate through the entries in a
dictionary using a for loop. This for-loop is enclosed by another loop
which traverses through a list and checks the relation between each
entry in the list and each entry in the dictionary.
while I know that dictionaries are 'unordered', I'd like to know if
the order of traversal will be the same each time the dictionary is
iterated through.
like if i have
dictionary={key1:"val1", key2:"val2",key3="val3"...}
for i in (1,10)
for value in dictionary1:
print value

You are aware that the above code iterates over the *keys*, not the values?

am i assured that i always get the same sequence of outputs for any
two values of i?

AFAIK the order is deterministic as long as you don't alter the dict between
iterations. However, this is an implementation detail. Why don't you just
do

for key in sorted(dictionary.keys()):
...

Diez

 

[Arnaud Delobelle]

You are aware that the above code iterates over the *keys*, not the values?


AFAIK the order is deterministic as long as you don't alter the dict between
iterations. However, this is an implementation detail. Why don't you just
do

for key in sorted(dictionary.keys()):

That would work only if the keys are sortable, and would be wasteful
because you would need to sort the keys for each value of i. A better
method may be to extract the keys before iterating over i:

keys = list(dictionary)

for i in 1, 10:
for key in keys:
...

Then you know that keys will be iterated over in the same order.

 

[Carsten Haese]

AFAIK the order is deterministic as long as you don't alter the dict between
iterations. However, this is an implementation detail.

It's not an implementation detail. It's documented behavior. Thus quoth
http://docs.python.org/library/stdtypes.html#mapping-types-dict :

"""
If items(), keys(), values(), iteritems(), iterkeys(), and itervalues()
are called with no intervening modifications to the dictionary, the
lists will directly correspond.
"""

 

[John Machin]

It's not an implementation detail. It's documented behavior. Thus quothhttp://docs.python.org/library/stdtypes.html#mapping-types-dict:

"""
If items(), keys(), values(), iteritems(), iterkeys(), and itervalues()
are called with no intervening modifications to the dictionary, the
lists will directly correspond.
"""

Changing the value attached to an existing key is a "modification to
the dictionary", but it's hard to see how that would change the
iteration order.

"the lists will directly correspond"? What does that mean? Why not
"the lists will be equal i.e. list1 == list2"?

How about "Provided that keys are neither added nor deleted, the order
of iteration will not change"?

 

[python]

Is there a formula for determining the approximate size of a dictionary
(minus its data) under 32 and 64 bit Python with a specific average key
size?

For instance, if we were running a 64-bit version of Python and created
a dictionary of 1 million items with an average key length of 48 bytes,
is there a way to calculate how much memory this type of dictionary
would consume on average? I understand that there will be overhead for
the amount of information that each dictionary entry holds - I'm just
trying to get a handle on how much memory a given dictionary's basic
structure will require.

My understanding is that Python stores both the hash value of the key
and the key itself plus 2 pointers: a key pointer and a value pointer.
I'm guessing that dictionary keys are stored as either 4 or 8 byte
values. So my back of the napkin estimate is that there each dictionary
entry under a 64 bit version of Python would be 24 bytes + the original
key.

Malcolm

 

[Carsten Haese]

"the lists will directly correspond"? What does that mean?

It means that e.g. zip(d.keys(), d.values()) == d.items() is guaranteed
to be True.

Why not
"the lists will be equal i.e. list1 == list2"?

How about "Provided that keys are neither added nor deleted, the order
of iteration will not change"?

Neither of those convey the above guarantee.

 

[Steven D'Aprano]

Is there a formula for determining the approximate size of a dictionary
(minus its data) under 32 and 64 bit Python with a specific average key
size?

If you're using Python 2.6, the sys module has a new function getsizeof()
which returns the number of bytes used by an object.

You can also look at this recipe:

http://code.activestate.com/recipes/546530/

This question has been asked before. See:

http://mail.python.org/pipermail/python-list/2008-January/472683.html
http://mail.python.org/pipermail/python-list/2002-March/135223.html

and probably others.

 

[Rhamphoryncus]

Changing the value attached to an existing key is a "modification to
the dictionary", but it's hard to see how that would change the
iteration order.

Although the referenced docs don't clarify it, changing the value
without adding or removing a key (even temporarily) does NOT reorder
the dict. This has been declared officially on python-dev.

"the lists will directly correspond"? What does that mean? Why not
"the lists will be equal i.e. list1 == list2"?

How about "Provided that keys are neither added nor deleted, the order
of iteration will not change"?

Python 3.0 never returns lists directly (it provides views), so the
wording has already been tweaked.

 

[python]

Steven,

Wonderful! You and your references answered all my questions.

I had missed 2.6's new getsizeof() function. Yet another reason to do
the 2.5-to-2.6 upgrade.

Regards,
Malcolm