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

Discussion in 'Python' started by Priya, Nov 21, 2008.

  1. Priya

    Priya Guest

    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.
    Priya, Nov 21, 2008
    #1
    1. Advertising

  2. Priya wrote:

    > 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
    Diez B. Roggisch, Nov 21, 2008
    #2
    1. Advertising

  3. "Diez B. Roggisch" <> writes:

    > Priya wrote:
    >
    >> 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()):


    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.

    --
    Arnaud
    Arnaud Delobelle, Nov 21, 2008
    #3
  4. Diez B. Roggisch wrote:
    > 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.
    """

    --
    Carsten Haese
    http://informixdb.sourceforge.net
    Carsten Haese, Nov 24, 2008
    #4
  5. Priya

    John Machin Guest

    On Nov 24, 11:59 am, Carsten Haese <> wrote:
    > Diez B. Roggisch wrote:
    > > 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 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"?
    John Machin, Nov 24, 2008
    #5
  6. Priya

    Guest

    Estimating size of dictionary

    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
    , Nov 24, 2008
    #6
  7. John Machin wrote:
    > "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.

    --
    Carsten Haese
    http://informixdb.sourceforge.net
    Carsten Haese, Nov 24, 2008
    #7
  8. Re: Estimating size of dictionary

    On Sun, 23 Nov 2008 21:10:34 -0500, python wrote:

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



    --
    Steven
    Steven D'Aprano, Nov 24, 2008
    #8
  9. On Nov 23, 6:43 pm, John Machin <> wrote:
    > On Nov 24, 11:59 am, Carsten Haese <> wrote:
    >
    > > Diez B. Roggisch wrote:
    > > > 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 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.


    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.
    Rhamphoryncus, Nov 24, 2008
    #9
  10. Priya

    Guest

    Re: Estimating size of dictionary

    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
    , Nov 24, 2008
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Annick
    Replies:
    0
    Views:
    441
    Annick
    Aug 6, 2003
  2. CSUIDL PROGRAMMEr

    Time depended java program

    CSUIDL PROGRAMMEr, Apr 27, 2006, in forum: Java
    Replies:
    2
    Views:
    308
    Roedy Green
    Apr 27, 2006
  3. Ilias Lazaridis
    Replies:
    6
    Views:
    433
    Ilias Lazaridis
    Feb 21, 2006
  4. =?ISO-8859-2?Q?Grzegorz_=A6lusarek?=

    formEncode and validation depended on forms field

    =?ISO-8859-2?Q?Grzegorz_=A6lusarek?=, May 17, 2006, in forum: Python
    Replies:
    0
    Views:
    264
    =?ISO-8859-2?Q?Grzegorz_=A6lusarek?=
    May 17, 2006
  5. Don Bruder
    Replies:
    3
    Views:
    963
    spikeysnack
    Aug 3, 2010
Loading...

Share This Page