Regarding Dictionaries in python
Mehta, Anish
I am having a small query regarding dictionaries in python. From
Orelly's Programming Python
>>>D= {'a' : 1, 'b' : 2, 'c' : 3, 'd' : 4}
>>>D.items()
[ ('b', 2), ('c', 3), ('d', 4), ('a', 1)]
why it is not showing the items in order in which i have inserted.
Please tell me why it is happing like this.
Thanks in advance.
Regards...
John Hall
<Anish...@enst-bretagne.fr> wrote:
>why it is not showing the items in order in which i have inserted.
>Please tell me why it is happing like this.
Because the order of items in dictionaries is inherently undefined, or
whimsical if you prefer. Your book should tell you that, but of course
you need to read the relevant sentence.
There are cookbook recipes for sorting them if you really need to.
--
John W Hall <wweexxss...@telusplanet.net>
Calgary, Alberta, Canada.
"Helping People Prosper in the Information Age"
laotseu
Because dictionnaries in python are not ordered. I think (not sure
but...) this is in the Python doc...
Laotseu
David Eppstein
"Mehta, Anish" <Anish...@enst-bretagne.fr> wrote:
> why it is not showing the items in order in which i have inserted.
> Please tell me why it is happing like this.
Because dictionaries store things out-of-order, in hash tables, so that
they can perform lookups quickly. If maintaining the order of some
things is important, that's what lists are for.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Andy Jewell
> Hello !
>
> I am having a small query regarding dictionaries in python. From
> Orelly's Programming Python
>
> >>>D= {'a' : 1, 'b' : 2, 'c' : 3, 'd' : 4}
> >>>D.items()
>
> [ ('b', 2), ('c', 3), ('d', 4), ('a', 1)]
>
>
> Please tell me why it is happing like this.
>
>
> Regards...
Dictionaries are not ordered entities - check the Tutorial. They use a
hashing algorithm to retrieve items, and as items are added, they are stored
in a 'bucket' that is unique to that item. The order of the buckets cannot
be influenced (it's coded into Python). For details on how hashing
algorithms work, scan google...
Numeric items are always added in ascending order (as far as my little
experiments showed anyway):
>>> d={}
>>> d[1]="one"
>>> d
{1: 'one'}
>>> d[2]="two"
>>> d
{1: 'one', 2: 'two'}
>>> d[3]="three"
>>> d
{1: 'one', 2: 'two', 3: 'three'}
>>> d[4]="four"
>>> d
{1: 'one', 2: 'two', 3: 'three', 4: 'four'}
String values are added in a manner appropriate for sequences:
>>> for l in "abcdef":
d[l]=l
print d
{'a': 'a'}
{'a': 'a', 'b': 'b'}
{'a': 'a', 'c': 'c', 'b': 'b'}
{'a': 'a', 'c': 'c', 'b': 'b', 'd': 'd'}
{'a': 'a', 'c': 'c', 'b': 'b', 'e': 'e', 'd': 'd'}
{'a': 'a', 'c': 'c', 'b': 'b', 'e': 'e', 'd': 'd', 'f': 'f'}
{'a': 'a', 'c': 'c', 'b': 'b', 'e': 'e', 'd': 'd', 'g': 'g', 'f': 'f'}
I'd imagine tuples are handled similarly, but I haven't tried them...
Hope that helps.
-andyj
Steven Taschuk
[...]
> Dictionaries are not ordered entities - check the Tutorial. [...]
> Numeric items are always added in ascending order (as far as my little
> experiments showed anyway):
>
> >>> d={}
> >>> d[1]="one"
> >>> d
> {1: 'one'}
> >>> d[2]="two"
> >>> d
> {1: 'one', 2: 'two'}
This happy sorting of int keys works in simple cases, but it is
very fragile and should not be relied on.
When it works, it's because (a) ints are their own hash values,
(b) entries are by preference placed at index hash(key) in the
underlying table, and (c) iteration over the dict occurs in the
order of the underlying table.
But even if the keys' hash function preserves order (as ints'
does, if we ignore negative values), the ordering can be broken if
hash(key) is larger than the table size (which is always a power
of 2, I think):
>>> d = {6: 'foo'}
>>> d[65536] = 'bar' # stored at index 65536 % tablesize == 0
>>> d
{65536: 'bar', 6: 'foo'}
Further, when a new key's hash is larger than the table size, it
might collide with an existing entry; in this case the new entry
has to be placed elsewhere. The selection of the elsewhere is
complicated (see comments in Objects/dictobject.c), and can easily
break the sorting. This kind of breakage depends not only on the
hash values, but on the order of insertion:
>>> d = {}
>>> d[23] ='foo'
>>> d[7] = 'bar' # collides with 23
>>> d # appears sorted anyway
{7: 'bar', 23: 'foo'}
>>> d = {}
>>> d[7] = 'bar'
>>> d[23] = 'foo' # collides with 7
>>> d # dis-sorted
{23: 'foo', 7: 'bar'}
Moreover, this kind of breakage may go unnoticed until more
elements are added to the dict:
>>> d = {}
>>> d[2] = 'foo'
>>> d[18] = 'bar' # collides with 2
>>> d # appears sorted anyway, until...
{2: 'foo', 18: 'bar'}
>>> d[5] = 'snee'
>>> d
{2: 'foo', 18: 'bar', 5: 'snee'}
In other words, do not be deceived by simple tests of this matter!
--
Steven Taschuk stas...@telusplanet.net
"Study this book; read a word then ponder on it. If you interpret the meaning
loosely you will mistake the Way." -- Musashi, _A Book of Five Rings_
Anton Vredegoor
> >>>D= {'a' : 1, 'b' : 2, 'c' : 3, 'd' : 4}
> >>>D.items()
>[ ('b', 2), ('c', 3), ('d', 4), ('a', 1)]
>
>
>why it is not showing the items in order in which i have inserted.
>Please tell me why it is happing like this.
Others have already explained this phenomenon. I would like to add
that the language designers do not guarantee that dictionaries will
always return their items in the same order across implementations.
So, for example on another Python interpreter:
Python 2.2.1 (#1, Jun 25 2002, 10:55:46)
[GCC 2.95.3-5 (cygwin special)] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> D= {'a' : 1, 'b' : 2, 'c' : 3, 'd' : 4}
>>> D.items()
[('a', 1), ('c', 3), ('b', 2), ('d', 4)]
>>>
This gives the language designers enough flexibility to always provide
us with "state of the art" implementations of the dictionary type.
At the same time this makes the dictionary type the place where Python
hides most of its ambiguity.
Anton