Is numeric keys of Python's dictionary automatically sorted?

Discussion in 'Python' started by John, Mar 7, 2007.

  1. John

    John Guest

    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 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?
     
    John, Mar 7, 2007
    #1
    1. Advertisements

  2. John

    Ant Guest

    "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.
     
    Ant, Mar 7, 2007
    #2
    1. Advertisements

  3. John

    John Guest

    Then is there anyway to sort the numeric keys and avoid future implemetation
    confusion?
     
    John, Mar 7, 2007
    #3
  4. 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:
    {100000: [], 1: [], 100: [], 1000: [], 10: [], 10000: []}

    -Carsten
     
    Carsten Haese, Mar 7, 2007
    #4
  5. John

    Robert Kern Guest

    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
     
    Robert Kern, Mar 7, 2007
    #5
  6. 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.
     
    Nick Vatamaniuc, Mar 8, 2007
    #6
  7. 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.

    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.


    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.

    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:
    {1: None, 2: None, 3: None}

    and concludes that dictionaries are ordered. If they are better-than
    average, they might try this:
    {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, 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, Mar 8, 2007
    #7
  8. John

    Duncan Booth Guest

    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:
    {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, Mar 8, 2007
    #8
  9. John

    Duncan Booth Guest

    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.
     
    Duncan Booth, Mar 8, 2007
    #9
  10. John

    Paul Rubin Guest

    Why are you coding a radix sort?
    Just an accident, dicts are implemented using hashing, and small
    integers hash to themselves.
     
    Paul Rubin, Mar 8, 2007
    #10


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

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

    Matthias
     
    Matthias Julius, Mar 8, 2007
    #11
  12. John

    Ant Guest

    On Mar 8, 8:20 am, Steven D'Aprano <>
    wrote:
    ....
    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.
     
    Ant, Mar 8, 2007
    #12
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.