Ordered dictionary?

Discussion in 'Python' started by Leif K-Brooks, Jan 22, 2004.

  1. 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.
     
    Leif K-Brooks, Jan 22, 2004
    #1
    1. Advertising

  2. 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
     
    Josiah Carlson, Jan 22, 2004
    #2
    1. Advertising

  3. Leif K-Brooks

    John Hunter Guest

    >>>>> "Leif" == Leif K-Brooks <> 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
     
    John Hunter, Jan 22, 2004
    #3
  4. # 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
     
    Jonathan Daugherty, Jan 22, 2004
    #4
  5. Leif K-Brooks

    Paul McGuire Guest

    "Leif K-Brooks" <> wrote in message
    news:leWPb.231$...
    > 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
     
    Paul McGuire, Jan 22, 2004
    #5
  6. 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...
     
    Leif K-Brooks, Jan 22, 2004
    #6
  7. Leif K-Brooks

    BW Glitch Guest

    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"
     
    BW Glitch, Jan 22, 2004
    #7
  8. Leif K-Brooks

    BW Glitch Guest

    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)
     
    BW Glitch, Jan 22, 2004
    #8
  9. Op 2004-01-22, Paul McGuire schreef <>:
    > "Leif K-Brooks" <> wrote in message
    > news:leWPb.231$...
    >> 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
     
    Antoon Pardon, Jan 23, 2004
    #9
  10. 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 <>:
    > > "Leif K-Brooks" <> wrote in message
    > > news:leWPb.231$...
    > >> 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
    >
     
    Dragos Chirila, Jan 23, 2004
    #10
  11. 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
     
    Carmine Moleti, Jan 23, 2004
    #11
  12. Leif K-Brooks

    Terry Reedy Guest

    > 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
     
    Terry Reedy, Jan 23, 2004
    #12
  13. 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
     
    Josiah Carlson, Jan 23, 2004
    #13
  14. "Paul McGuire" <> 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.
     
    David M. Wilson, Jan 23, 2004
    #14
    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. Tom Anderson
    Replies:
    0
    Views:
    320
    Tom Anderson
    Nov 26, 2005
  2. pyGuy
    Replies:
    2
    Views:
    305
    pyGuy
    Apr 12, 2006
  3. Navkirat Singh
    Replies:
    6
    Views:
    3,067
    Navkirat Singh
    Jul 29, 2010
  4. Chris Rebert
    Replies:
    0
    Views:
    529
    Chris Rebert
    Jul 29, 2010
  5. DL

    Ordered list inside ordered list

    DL, Nov 9, 2009, in forum: Javascript
    Replies:
    6
    Views:
    327
    Dr J R Stockton
    Nov 21, 2009
Loading...

Share This Page