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 4 1889
In <11************ **********@h2g2 000hsg.googlegr oups.com>, jm*******@no.sp am.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
On May 15, 6:33 pm, Marc 'BlackJack' Rintsch <bj_...@gmx.net wrote:
In <1179233407.473 173.259...@h2g2 000hsg.googlegr oups.com>,
jm.sur...@no.sp am.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
In <11************ ********@e51g20 00hsg.googlegro ups.com>, jm*******@no.sp am.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
On May 15, 9:25 pm, Marc 'BlackJack' Rintsch <bj_...@gmx.net wrote:
In <1179243655.596 897.6...@e51g20 00hsg.googlegro ups.com>,
jm.sur...@no.sp am.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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Dave |
last post by:
Hello all,
After perusing the Standard, I believe it is true to say that once you
insert an element into a std::list<>, its location in memory never changes.
This makes a std::list<> ideal for storing vertices of an arbitrary n-ary
tree where a vertex contain pointers to its parent / children. These parent
/ child vertices need to stay put if we've got pointers to them somewhere!
Am I correct in my assertion?
|
by: pmcguire |
last post by:
I have a treeview with a lot of nodes. I want to load only the nodes that are initially visible when the form loads, and then continue to populate it in background and/or when the nodes are required by the user either scrolling or performing some other action that would move the treeview window to a particular "unloaded" node in the treeview
Any advice on how to go about this? It seems I need a way of sensing a scroll event in the treeview...
|
by: Alex D. |
last post by:
is it possible? pros and cons?
|
by: Brian Tkatch |
last post by:
I have a form that has six possible setups for a TreeView, though after
the Tree is shown, they all act the same way. The Nodes have three or
four levels.
Repopulating the tree for another setup takes a moment due to the logic
involved in populating it. I am wondering it it would be faster if i
could "save" the nodes for later.
CopyTo and AddRange seem to support one level. Is there soimething
similar for a multi-dimensional array?
|
by: LacrosseB0ss |
last post by:
Hey all!
I have just started using the TreeView object in asp. There are some other applications I have seen use it and I have copied some of the code from them at work. What happens is on a form, an item is selected from a dropdown box and based on what the user selects, there are items linked to that group in a different field. I would like these items to show up as tree view nodes split aplhabetically.
This works fine. The grandparent...
| |
by: Gigs_ |
last post by:
Hi all!
I have text file (english-croatian dictionary) with words in it in alphabetical
order.
This file contains 179999 words in this format:
english word: croatian word
I want to make instant search for my gui
Instant search, i mean that my program search words and show words to user as
user type letters.
|
by: John Rogers |
last post by:
This code only counts the parent nodes or rootnodes in a treeview,
how do you count all the nodes in a treeview?
// one way
int NodeCounter = 0;
foreach (TreeNode currentNode in TreeView1.Nodes)
NodeCounter++;
// other way
int total = TreeView1.Nodes.Count;
|
by: Sl1ver |
last post by:
I've got a problem, i got the nodes to move but
1. they copy nodes(if you drag it to 3 different places it will actually have 3 of the same nodes)
2. i want to make the nodes, if moved update the new nodes locations
This is my coding
private void tvDescriptions_MouseDown(object sender, MouseEventArgs e)
{
TreeView tree = (TreeView)sender;
|
by: kajuchirag |
last post by:
How do i store the date and tree root node and child nodes in database.
How many tables to be created.
It should be fast in counting the nodes even if there are more than 25000 child nodes in left or right.
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
| |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |