On May 15, 6:33 pm, Marc 'BlackJack' Rintsch <[EMAIL PROTECTED]> wrote:
> In <[EMAIL PROTECTED]>,
>
>
>
> [EMAIL PROTECTED] wrote:
> > I use these names as keys in a dictionary, and store node's data.
> > Now given a name like "abc", I want to find the key with the following
> > rule:
> > If the key exists return the value
> > If the key does not exist, return the value of the leaf node whose
> > name is in the given name. For, "abc", it is "ab" . For, "ad", it is
> > "a".
>
> > I suppose there must be a simpler solution to this problem. I
> > implemented it like this:
> > d = {'a':0, 'aa':12, 'ab':43, 'aaa':22, 'aab':343, 'ac':33}
> > name = 'abc'
> > key = max( [ x for x in d.iterkeys() if x in name] )
> > value = d[key]
>
> > I can change the data structure from dictinory to tuple of key,value
> > pairs or any thing, and afford to keep them in a particular order. Is
> > there any way I can speed up this as I have to do this for around 4000
> > times with tree size being ~5000.
>
> What about this:
>
> def search(tree, path):
> while path:
> result = tree.get(path)
> if result is not None:
> return result
> path = path[:-1]
> raise KeyError('path not on tree')
>
> Ciao,
> Marc 'BlackJack' Rintsch
If I have the tree in the dictionary, the code would like this,
def search(tree, path):
while path and not(tree.haskey(path)):
path = path[:-1]
if path:
return tree[path]
else:
raise KeyError('path not on tree')
Another qn -- dict.haskey() takes logn time, am I right?
-
Suresh
--
http://mail.python.org/mailman/listinfo/python-list
