Notice: Undefined variable: ref_badge_map_python_u_data_thin__team in /home/whirl/sites/grokbase/root/www/data/inc/incl.us_tbadges.php on line 36
[Python] Ordered dictionary? - Grokbase
FAQ

[Python] Ordered dictionary?

Leif K-Brooks
Jan 22, 2004 at 8:18 pm
I need to associate a string (key) with an integer (value). A dictionary
would do the job, except for the fact that it must be ordered. I also
need to look up the value for a specific key easily, so a list of tuples
wouldn't work.
reply

Search Discussions

14 responses

  • Josiah Carlson at Jan 22, 2004 at 8:27 pm

    Leif K-Brooks wrote:
    I need to associate a string (key) with an integer (value). A dictionary
    would do the job, except for the fact that it must be ordered. I also
    need to look up the value for a specific key easily, so a list of tuples
    wouldn't work.
    How must the dictionary be ordered? Do you need the keys or the values
    sorted?

    - Josiah
  • Leif K-Brooks at Jan 22, 2004 at 9:21 pm

    Josiah Carlson wrote:
    I need to associate a string (key) with an integer (value). A
    dictionary would do the job, except for the fact that it must be
    ordered. I also need to look up the value for a specific key easily,
    so a list of tuples wouldn't work.

    How must the dictionary be ordered? Do you need the keys or the values
    sorted?
    Sorry for not making that clear, I need it sorted by the order of
    insertion. Looks like
    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747 might do
    what I want...
  • BW Glitch at Jan 22, 2004 at 10:49 pm

    Leif K-Brooks wrote:

    Josiah Carlson wrote:
    I need to associate a string (key) with an integer (value). A
    dictionary would do the job, except for the fact that it must be
    ordered. I also need to look up the value for a specific key easily,
    so a list of tuples wouldn't work.


    How must the dictionary be ordered? Do you need the keys or the
    values sorted?

    Sorry for not making that clear, I need it sorted by the order of
    insertion. Looks like
    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747 might do
    what I want...
    That should do. Looks promising, but I think it uses the old style of
    extending the dictionary (Not that it's bad) ...

    --
    Glitch

    http://andres980.tripod.com/

    One good shot is worth a hundred bad ones!
    -- Big Shot (G1)
  • John Hunter at Jan 22, 2004 at 8:28 pm
    "Leif" == Leif K-Brooks <eurleif at ecritters.biz> writes:
    Leif> I need to associate a string (key) with an integer
    Leif> (value). A dictionary would do the job, except for the fact
    Leif> that it must be ordered. I also need to look up the value
    Leif> for a specific key easily, so a list of tuples wouldn't
    Leif> work.

    google : python ordered dictionary
    click : I'm feeling lucky

    JDH
  • Jonathan Daugherty at Jan 22, 2004 at 8:36 pm
    # I need to associate a string (key) with an integer (value). A dictionary
    # would do the job, except for the fact that it must be ordered. I also
    # need to look up the value for a specific key easily, so a list of tuples
    # wouldn't work.

    As the other posts on this thread suggest, dictionaries -- by virtue
    of their structure -- have no inherently meaningful ordering. You'll
    have to either sort the keys (the easy way) or design a wrapper for
    the dictionary that maintains a sorted list of the dictionary's
    keys and updates it as necessary (the hard way).

    --

    Jonathan Daugherty
    http://www.cprogrammer.org

    "It's a book about a Spanish guy called Manual, you should read it."
    -- Dilbert
  • Paul McGuire at Jan 22, 2004 at 9:19 pm
    "Leif K-Brooks" <eurleif at ecritters.biz> wrote in message
    news:leWPb.231$af7.162835 at newshog.newsread.com...
    I need to associate a string (key) with an integer (value). A dictionary
    would do the job, except for the fact that it must be ordered. I also
    need to look up the value for a specific key easily, so a list of tuples
    wouldn't work.
    If you really need to access the dictionary in sorted key order, is this so
    difficult?

    dKeys = d.keys()
    dKeys.sort()
    for k in dKeys:
    # do stuff with k and d[k], such as:
    print k, "=", d[k]

    Or if you are worried about updates to d between the time of key retrieval
    and time of traversal (for instance, if a separate thread were to delete one
    of the keyed entries), take a snapshot as a list:

    dItems = d.items() # from here on, you are insulated from changes to
    dictionary 'd'
    dItems.sort() # implicitly sorts by key
    dItems.sort( lambda a,b: a[1]-b[1] ) # sorts by value, if you so prefer
    for k,v in dItems:
    # do stuff with k and v, such as:
    print k, "=", v # <-- added benefit here of not re-accessing
    the list by key

    -- Paul
  • Antoon Pardon at Jan 23, 2004 at 9:16 am

    Op 2004-01-22, Paul McGuire schreef <ptmcg at users.sourceforge.net>:
    "Leif K-Brooks" <eurleif at ecritters.biz> wrote in message
    news:leWPb.231$af7.162835 at newshog.newsread.com...
    I need to associate a string (key) with an integer (value). A dictionary
    would do the job, except for the fact that it must be ordered. I also
    need to look up the value for a specific key easily, so a list of tuples
    wouldn't work.
    If you really need to access the dictionary in sorted key order, is this so
    difficult?

    dKeys = d.keys()
    dKeys.sort()
    for k in dKeys:
    # do stuff with k and d[k], such as:
    print k, "=", d[k]

    Or if you are worried about updates to d between the time of key retrieval
    and time of traversal (for instance, if a separate thread were to delete one
    of the keyed entries), take a snapshot as a list:

    dItems = d.items() # from here on, you are insulated from changes to
    dictionary 'd'
    dItems.sort() # implicitly sorts by key
    dItems.sort( lambda a,b: a[1]-b[1] ) # sorts by value, if you so prefer
    for k,v in dItems:
    # do stuff with k and v, such as:
    print k, "=", v # <-- added benefit here of not re-accessing
    the list by key
    Well I too sometimes need the keys in a dictionary to be sorted and your
    solutions wouldn't help. The problem is the following.

    I have a number of key value pairs, like names and telephone numbers.
    Just more subject to change. Now I want the telephone numbers of everyone
    whose name starts with "jan".

    Or I just inserted a name and want to know who is alphabetically next.
    Or I want to know who is first or last.

    --
    Antoon Pardon
  • Dragos Chirila at Jan 23, 2004 at 9:43 am
    Hi

    Maybe this code will help:

    import operator

    def filterList(p_list, p_value):
    l_len = len(p_list)
    l_temp = map(None, (p_value,)*l_len, p_list)
    l_temp = filter(lambda x: x[1].find(x[0])==0, l_temp)
    return map(operator.getitem, l_temp, (-1,)*len(l_temp))

    phones_dict = {'jansen' : '0000', 'xxx' : '1111', 'jan2' : '2222'}
    names_list = filterList(phones_dict.keys(), 'jan')
    phones_list = map(phones_dict.get, names_list)

    print phones_list

    This extracts from the dictionary the telephone(values) numbers for
    names(keys) starting with 'jan'...

    Dragos


    Op 2004-01-22, Paul McGuire schreef <ptmcg at users.sourceforge.net>:
    "Leif K-Brooks" <eurleif at ecritters.biz> wrote in message
    news:leWPb.231$af7.162835 at newshog.newsread.com...
    I need to associate a string (key) with an integer (value). A
    dictionary
    would do the job, except for the fact that it must be ordered. I also
    need to look up the value for a specific key easily, so a list of
    tuples
    wouldn't work.
    If you really need to access the dictionary in sorted key order, is this
    so
    difficult?

    dKeys = d.keys()
    dKeys.sort()
    for k in dKeys:
    # do stuff with k and d[k], such as:
    print k, "=", d[k]

    Or if you are worried about updates to d between the time of key
    retrieval
    and time of traversal (for instance, if a separate thread were to delete
    one
    of the keyed entries), take a snapshot as a list:

    dItems = d.items() # from here on, you are insulated from changes
    to
    dictionary 'd'
    dItems.sort() # implicitly sorts by key
    dItems.sort( lambda a,b: a[1]-b[1] ) # sorts by value, if you so
    prefer
    for k,v in dItems:
    # do stuff with k and v, such as:
    print k, "=", v # <-- added benefit here of not
    re-accessing
    the list by key
    Well I too sometimes need the keys in a dictionary to be sorted and your
    solutions wouldn't help. The problem is the following.

    I have a number of key value pairs, like names and telephone numbers.
    Just more subject to change. Now I want the telephone numbers of everyone
    whose name starts with "jan".

    Or I just inserted a name and want to know who is alphabetically next.
    Or I want to know who is first or last.

    --
    Antoon Pardon
    --
    http://mail.python.org/mailman/listinfo/python-list
  • Carmine Moleti at Jan 23, 2004 at 3:21 pm
    Hi Dragos,
    def filterList(p_list, p_value):
    l_len = len(p_list)
    l_temp = map(None, (p_value,)*l_len, p_list)
    l_temp = filter(lambda x: x[1].find(x[0])==0, l_temp)
    return map(operator.getitem, l_temp, (-1,)*len(l_temp))
    phones_dict = {'jansen' : '0000', 'xxx' : '1111', 'jan2' : '2222'}
    names_list = filterList(phones_dict.keys(), 'jan')
    phones_list = map(phones_dict.get, names_list)
    This extracts from the dictionary the telephone(values) numbers for
    names(keys) starting with 'jan'...
    Why you didn't used the string.startswith(...) method?

    I wrote this:

    d={'carmine':'123456','carmela':'4948399','pippo':'39938303'}
    for name,number in d.items():
    if name.startswith('car'):
    print name,number

    This also extract from the dictionay all the (name,number) pairs whose
    name starts with a given substring ('car' in the example).

    Thanks for your answer
  • Josiah Carlson at Jan 23, 2004 at 7:55 pm

    Carmine Moleti wrote:

    Hi Dragos,

    def filterList(p_list, p_value):
    l_len = len(p_list)
    l_temp = map(None, (p_value,)*l_len, p_list)
    l_temp = filter(lambda x: x[1].find(x[0])==0, l_temp)
    return map(operator.getitem, l_temp, (-1,)*len(l_temp))
    phones_dict = {'jansen' : '0000', 'xxx' : '1111', 'jan2' : '2222'}
    names_list = filterList(phones_dict.keys(), 'jan')
    phones_list = map(phones_dict.get, names_list)
    This extracts from the dictionary the telephone(values) numbers for
    names(keys) starting with 'jan'...

    Why you didn't used the string.startswith(...) method?

    I wrote this:

    d={'carmine':'123456','carmela':'4948399','pippo':'39938303'}
    for name,number in d.items():
    if name.startswith('car'):
    print name,number

    This also extract from the dictionay all the (name,number) pairs whose
    name starts with a given substring ('car' in the example).

    Thanks for your answer
    Something strange is that for short 'other' strings
    string[:len(other)] == other
    #is faster than
    string.startswith(other)

    Maybe find is faster than startswith.

    - Josiah
  • Terry Reedy at Jan 23, 2004 at 6:22 pm

    Well I too sometimes need the keys in a dictionary to be sorted and your
    solutions wouldn't help. The problem is the following.

    I have a number of key value pairs, like names and telephone numbers.
    Just more subject to change. Now I want the telephone numbers of everyone
    whose name starts with "jan".

    Or I just inserted a name and want to know who is alphabetically next.
    Or I want to know who is first or last.
    A python dict is not very well suited to this, especially for large numbers
    of key,value pairs. However, if you do pull out sorted lists of keys, use
    the bisect module to find specific keys. log(n) behavior is fine.

    A table with a btree index is designed for the things your want to do.
    There is a btree,py in zope (by Tim Peters, I believe), but I do not know
    how 'extractable' it is. You could search the archives.

    Terry J. Reedy
  • David M. Wilson at Jan 23, 2004 at 11:46 pm
    "Paul McGuire" <ptmcg at users.sourceforge.net> wrote...
    If you really need to access the dictionary in sorted key order, is this so
    difficult?
    That was not the original poster's question. Order is semantic
    information which a dictionary does not record or represent in any
    way.


    David.
  • Mel Wilson at Jan 27, 2004 at 4:56 pm
    In article <99dce321.0401231546.5f73d721 at posting.google.com>,
    dw-google.com at botanicus.net (David M. Wilson) wrote:
    "Paul McGuire" <ptmcg at users.sourceforge.net> wrote...
    If you really need to access the dictionary in sorted key order, is this so
    difficult?
    That was not the original poster's question. Order is semantic
    information which a dictionary does not record or represent in any
    way.
    Wants order of insertion. Best I can think of is



    class OrderedDict (dict):
    "Retains order-of-insertion in the dictionary"
    def __setitem__ (self, key, value):
    dict.__setitem__ (self, key, (len (self), value,) )

    def __getitem__ (self, key):
    return dict.__getitem__ (self, key)[1]

    def ordered_items (self):
    i = [(v, k) for (k, v) in self.items()]
    i.sort()
    return [(k, v[1]) for (v, k) in i]

    # end class OrderedDict

    if __name__ == '__main__':
    D = OrderedDict()
    D['oranges'] = 41
    D['lemons'] = 22
    D['limes'] = 63

    print D
    print D.ordered_items()



    Possibly other refinenemts: __init__ that inserts from a
    sequence of 2-tuples, keeping a sequence number as a class
    attribute instead of using len, etc.

    Regards. Mel.
  • BW Glitch at Jan 22, 2004 at 9:27 pm

    Leif K-Brooks wrote:

    I need to associate a string (key) with an integer (value). A dictionary
    would do the job, except for the fact that it must be ordered. I also
    need to look up the value for a specific key easily, so a list of tuples
    wouldn't work.
    A dictionary could be used. When you need to managed the items in order,
    what you would do is called dict.keys(), followed by a sort.

    I don't know if this helps at all...

    --
    Glitch

    http://andres980.tripod.com/

    "That is the law of the jungle. The hunters and the hunted. Scrap or
    be scrapped!"
    "Animals hunt to SURVIVE!"
    "And what do you think war is about?!"
    -- Dinobot and Tigatron, "The Law of the Jungle"

Related Discussions