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]

Re: Ordered dictionary?

Leif K-Brooks wrote:
[color=blue]
> 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.[/color]

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]

Re: Ordered dictionary?

Leif K-Brooks wrote:[color=blue]
> 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.[/color]

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

- Josiah

[John Hunter]

Re: Ordered dictionary?

>>>>> "Leif" == Leif K-Brooks <eurleif@ecritt ers.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]

Re: Ordered dictionary?

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

Re: Ordered dictionary?

"Leif K-Brooks" <eurleif@ecritt ers.biz> wrote in message
news:leWPb.231$ af7.162835@news hog.newsread.co m...[color=blue]
> 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.
>[/color]
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]

Re: Ordered dictionary?

Josiah Carlson wrote:[color=blue][color=green]
>> 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.[/color]
>
>
> How must the dictionary be ordered? Do you need the keys or the values
> sorted?[/color]

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]

Re: Ordered dictionary?

Leif K-Brooks wrote:
[color=blue]
> Josiah Carlson wrote:
>[color=green][color=darkred]
>>> 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.[/color]
>>
>>
>>
>> How must the dictionary be ordered? Do you need the keys or the
>> values sorted?[/color]
>
>
> 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...[/color]

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]

Re: Ordered dictionary?

Op 2004-01-22, Paul McGuire schreef <ptmcg@users.so urceforge.net>:[color=blue]
> "Leif K-Brooks" <eurleif@ecritt ers.biz> wrote in message
> news:leWPb.231$ af7.162835@news hog.newsread.co m...[color=green]
>> 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.
>>[/color]
> 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[/color]

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]

Re: Ordered dictionary?

Hi

Maybe this code will help:

import operator

def filterList(p_li st, p_value):
l_len = len(p_list)
l_temp = map(None, (p_value,)*l_le n, p_list)
l_temp = filter(lambda x: x[1].find(x[0])==0, l_temp)
return map(operator.ge titem, l_temp, (-1,)*len(l_temp) )

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

print phones_list

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

Dragos


[color=blue]
> Op 2004-01-22, Paul McGuire schreef <ptmcg@users.so urceforge.net>:[color=green]
> > "Leif K-Brooks" <eurleif@ecritt ers.biz> wrote in message
> > news:leWPb.231$ af7.162835@news hog.newsread.co m...[color=darkred]
> >> I need to associate a string (key) with an integer (value). A[/color][/color][/color]
dictionary[color=blue][color=green][color=darkred]
> >> 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[/color][/color][/color]
tuples[color=blue][color=green][color=darkred]
> >> wouldn't work.
> >>[/color]
> > If you really need to access the dictionary in sorted key order, is this[/color][/color]
so[color=blue][color=green]
> > 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[/color][/color]
retrieval[color=blue][color=green]
> > and time of traversal (for instance, if a separate thread were to delete[/color][/color]
one[color=blue][color=green]
> > of the keyed entries), take a snapshot as a list:
> >
> > dItems = d.items() # from here on, you are insulated from changes[/color][/color]
to[color=blue][color=green]
> > dictionary 'd'
> > dItems.sort() # implicitly sorts by key
> > dItems.sort( lambda a,b: a[1]-b[1] ) # sorts by value, if you so[/color][/color]
prefer[color=blue][color=green]
> > for k,v in dItems:
> > # do stuff with k and v, such as:
> > print k, "=", v # <-- added benefit here of not[/color][/color]
re-accessing[color=blue][color=green]
> > the list by key[/color]
>
> 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
>[/color]

[Carmine Moleti]

Re: Ordered dictionary?

Hi Dragos,
[color=blue]
> def filterList(p_li st, p_value):
> l_len = len(p_list)
> l_temp = map(None, (p_value,)*l_le n, p_list)
> l_temp = filter(lambda x: x[1].find(x[0])==0, l_temp)
> return map(operator.ge titem, l_temp, (-1,)*len(l_temp) )[/color]
[color=blue]
> phones_dict = {'jansen' : '0000', 'xxx' : '1111', 'jan2' : '2222'}
> names_list = filterList(phon es_dict.keys(), 'jan')
> phones_list = map(phones_dict .get, names_list)[/color]
[color=blue]
> This extracts from the dictionary the telephone(value s) numbers for
> names(keys) starting with 'jan'...[/color]

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

I wrote this:

d={'carmine':'1 23456','carmela ':'4948399','pi ppo':'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]

Re: Ordered dictionary?

Carmine Moleti wrote:
[color=blue]
> Hi Dragos,
>
>[color=green]
>>def filterList(p_li st, p_value):
>> l_len = len(p_list)
>> l_temp = map(None, (p_value,)*l_le n, p_list)
>> l_temp = filter(lambda x: x[1].find(x[0])==0, l_temp)
>> return map(operator.ge titem, l_temp, (-1,)*len(l_temp) )[/color]
>
>[color=green]
>>phones_dict = {'jansen' : '0000', 'xxx' : '1111', 'jan2' : '2222'}
>>names_list = filterList(phon es_dict.keys(), 'jan')
>>phones_list = map(phones_dict .get, names_list)[/color]
>
>[color=green]
>>This extracts from the dictionary the telephone(value s) numbers for
>>names(keys) starting with 'jan'...[/color]
>
>
> Why you didn't used the string.startswi th(...) method?
>
> I wrote this:
>
> d={'carmine':'1 23456','carmela ':'4948399','pi ppo':'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[/color]

Something strange is that for short 'other' strings
string[:len(other)] == other
#is faster than
string.startswi th(other)

Maybe find is faster than startswith.

- Josiah

[David M. Wilson]

Re: Ordered dictionary?

"Paul McGuire" <ptmcg@users.so urceforge.net> wrote...
[color=blue]
> If you really need to access the dictionary in sorted key order, is this so
> difficult?[/color]

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]

Re: Ordered dictionary?

> Well I too sometimes need the keys in a dictionary to be sorted and your[color=blue]
> 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[/color]
everyone[color=blue]
> 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.[/color]

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]

Re: Ordered dictionary?

In article <99dce321.04012 31546.5f73d721@ posting.google. com>,
dw-google.com@bota nicus.net (David M. Wilson) wrote:[color=blue]
>"Paul McGuire" <ptmcg@users.so urceforge.net> wrote...
>[color=green]
>> If you really need to access the dictionary in sorted key order, is this so
>> difficult?[/color]
>
>That was not the original poster's question. Order is semantic
>information which a dictionary does not record or represent in any
>way.[/color]

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.