Ordered dictionary?

[Leif K-Brooks]

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.

[BW Glitch]

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"

[Josiah Carlson]

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

[John Hunter]

>>>>> "Leif" == Leif K-Brooks <eu*****@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]

# 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]

"Leif K-Brooks" <eu*****@ecritters.biz> wrote in message
news:le******************@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

[Leif K-Brooks]

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/Coo.../Recipe/107747 might do
what I want...

[BW Glitch]

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/Coo.../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)

[Antoon Pardon]

Op 2004-01-22, Paul McGuire schreef <pt***@users.sourceforge.net>:

"Leif K-Brooks" <eu*****@ecritters.biz> wrote in message
news:le******************@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]

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 <pt***@users.sourceforge.net>:

"Leif K-Brooks" <eu*****@ecritters.biz> wrote in message
news:le******************@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]

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]

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

[David M. Wilson]

"Paul McGuire" <pt***@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.

[Terry Reedy]

> 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

[Mel Wilson]

In article <99**************************@posting.google.com >,
dw***********@botanicus.net (David M. Wilson) wrote:

"Paul McGuire" <pt***@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.