Ordered Dictionaries? Trees?
jepler epler
jepler.lnk at lnk.ispi.net
Mon Sep 4 22:02:39 EDT 2000
On Mon, 04 Sep 2000 13:31:16 -0700, Stephen Hansen
<stephen at cerebralmaelstrom.com> wrote:
>I need a Dictionary who's order is perdictable and/or settable; e.g.
>FIFO/LILO... For instance, if I do: dict['A'] = 1, dict['C'] = 2, dict['B'] = 3,
>then dict.keys() would return ('A','C','B'), always. :)
Something like (untested and incomplete)
class OrderedDict:
def __init__(self):
self.data = []
self.names = []
def __setitem__(self, item, value):
if item in self.names:
self.data[self.names.index(item)] = value
else:
self.names.append(item)
self.data.append(names)
def __getitem__(self, item):
if item in self.names:
return self.data[self.names.index(item)]
else:
raise KeyError, item
def keys(self):
return self.names[:]
def values(self):
return self.data[:]
def items(self):
return map(tuple, self.names, self.data)
>
>What's the best way to do this,
>that isn't tooooooo terribly slow? Speed isn't urgent, but hey, i'd rather
>it not become a negative later on as things expand.
Remember: encapsulate behavior in a class; if performance becomes a problem,
rewrite the class as a C extension. Performance of the above code is likely
not too great, since 'item in list' and 'list.index(item)' are linear in the
number of items. Instead, you might make 'names' be a native dict, with keys
equal to the keys of your ordered dictionary, and values equal to the index
of the key. But in that case, deleting a key can be an expensive operation.
Jeff
More information about the Python-list
mailing list