Storing and searching nodes of a tree

[jm.suresh]

Hi, I have a tree data structure and I name each node with the
following convention:

a
|---aa
| |--- aaa
| |--- aab
|
|---ab
|
|---ac
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.

-
Suresh

[Marc 'BlackJack' Rintsch]

In <11**********************@h2g2000hsg.googlegroups. com>,
jm*******@no.spam.gmail.com 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

[jm.suresh]

On May 15, 6:33 pm, Marc 'BlackJack' Rintsch <[e-mail]:

In <[e-mail]. com>,

[e-mail] 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

[Marc 'BlackJack' Rintsch]

In <11********************@e51g2000hsg.googlegroups.c om>,
jm*******@no.spam.gmail.com wrote:

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?

No it's O(1). Dictionaries are implemented as hash tables. You may write
the condition as:

while path and path not in tree:

That's a little easier to read and a bit faster too as a method lookup is
spared.

Ciao,
Marc 'BlackJack' Rintsch

[jm.suresh]

On May 15, 9:25 pm, Marc 'BlackJack' Rintsch <[e-mail]:

In <[e-mail].c om>,

[e-mail] wrote:

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?

No it's O(1). Dictionaries are implemented as hash tables. You may write
the condition as:

while path and path not in tree:

That's a little easier to read and a bit faster too as a method lookup is
spared.

Ciao,
Marc 'BlackJack' Rintsch

Wow :) , thanks.
-
Suresh