By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,996 Members | 1,498 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,996 IT Pros & Developers. It's quick & easy.

Storing and searching nodes of a tree

P: n/a
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

May 15 '07 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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
May 15 '07 #2

P: n/a
On May 15, 6:33 pm, Marc 'BlackJack' Rintsch <bj_...@gmx.netwrote:
In <1179233407.473173.259...@h2g2000hsg.googlegroups. com>,

jm.sur...@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
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

May 15 '07 #3

P: n/a
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
May 15 '07 #4

P: n/a
On May 15, 9:25 pm, Marc 'BlackJack' Rintsch <bj_...@gmx.netwrote:
In <1179243655.596897.6...@e51g2000hsg.googlegroups.c om>,

jm.sur...@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
Wow :) , thanks.
-
Suresh

May 15 '07 #5

This discussion thread is closed

Replies have been disabled for this discussion.