Hashtable - Get picked values
-
I have a Hashtable with following values: [Key][Value] [$0001][1] [$0002][0] [$0003][1] [$0004][0] [$0005][0] [$0006][0] [$0007][1] [$0008][1] [$0009][1] [$0010][1] Now I need all Keys with value "1". It is possible to extract them without a for loop? My main problem is a recursion. This hashtable is used 4 times and I have to check each key. Hashtable contains ~800 entries, what means 800^4 possibilites. Big overhead. Simple example: [$0001][00] [$0002][01] [$0003][04] [$0004][01] [$0005][02] Recursion - check element and its connectors 1. 0001 - my for loop checks all connectors -> Result: 0002 and 0004 (because Key is 01). 2. now check the connectors for connectors (we have 0002 and 0004) 3. 0002 has 0005(key = 02) and so on ..... Is there a way for a fast progress in speed? Thanks for all tips.
Seraphin wrote:
Now I need all Keys with value "1". It is possible to extract them without a for loop?
No. Use the values as keys into another hashtable where the values are arrays. I don't think .NET has multimaps. Christian Graus - Microsoft MVP - C++
-
Seraphin wrote:
Now I need all Keys with value "1". It is possible to extract them without a for loop?
No. Use the values as keys into another hashtable where the values are arrays. I don't think .NET has multimaps. Christian Graus - Microsoft MVP - C++
-
Hi Chris, Thanks for reply. Values are not unique, so it's a little bit hard to realize that. The big problem is to check each key with all available keys (so keys^keys possibilities) to find connectors. Speed is really hard task.
I know values are not unique, that's why I said to store an array list against each key, so you have an array of values for each. Christian Graus - Microsoft MVP - C++
-
I know values are not unique, that's why I said to store an array list against each key, so you have an array of values for each. Christian Graus - Microsoft MVP - C++
OK, but I have still a problem with overhead. Look at this link and look at those trees. http://personal.vsnl.com/erwin/pruning.htm[^] Level 1 Level 2 and so on. My hashtable uses 4 levels and each node needs ALL nodes from the upper levels to check. Level 1 has 800 entries. Level 2 has 800x800 entries and so on, which makes me crazy.
-
OK, but I have still a problem with overhead. Look at this link and look at those trees. http://personal.vsnl.com/erwin/pruning.htm[^] Level 1 Level 2 and so on. My hashtable uses 4 levels and each node needs ALL nodes from the upper levels to check. Level 1 has 800 entries. Level 2 has 800x800 entries and so on, which makes me crazy.
Seraphin wrote:
each node needs ALL nodes from the upper levels to check.
OK - in that case you probably want to look for a more optimised solution. Christian Graus - Microsoft MVP - C++
-
Seraphin wrote:
each node needs ALL nodes from the upper levels to check.
OK - in that case you probably want to look for a more optimised solution. Christian Graus - Microsoft MVP - C++
-
I have a Hashtable with following values: [Key][Value] [$0001][1] [$0002][0] [$0003][1] [$0004][0] [$0005][0] [$0006][0] [$0007][1] [$0008][1] [$0009][1] [$0010][1] Now I need all Keys with value "1". It is possible to extract them without a for loop? My main problem is a recursion. This hashtable is used 4 times and I have to check each key. Hashtable contains ~800 entries, what means 800^4 possibilites. Big overhead. Simple example: [$0001][00] [$0002][01] [$0003][04] [$0004][01] [$0005][02] Recursion - check element and its connectors 1. 0001 - my for loop checks all connectors -> Result: 0002 and 0004 (because Key is 01). 2. now check the connectors for connectors (we have 0002 and 0004) 3. 0002 has 0005(key = 02) and so on ..... Is there a way for a fast progress in speed? Thanks for all tips.
Seraphin wrote:
Simple example: [$0001][00] [$0002][01] [$0003][04] [$0004][01] [$0005][02] Recursion - check element and its connectors 1. 0001 - my for loop checks all connectors -> Result: 0002 and 0004 (because Key is 01).
Just so I understand, you're starting with a value of (00)01 and asking which keys have this value? The result in this case being $0002 and $0004?
Seraphin wrote:
2. now check the connectors for connectors (we have 0002 and 0004) 3. 0002 has 0005(key = 02) and so on .....
So having gotten the $0002 and $0004 keys, you are now interested in which keys have those two keys as values? This suggestion may be exactly what Christian suggested, but I would switch things around and use the values as keys and the keys as values. Each key would have an array of values. It would look like this: [00][$0001] [01][$0002][$0004] [04][$0003] [02][$0005] Asking the question again, which value(s) correspond to the 01 key? Answer: $0002 and $0004. Which value(s) correspond to the key 02? Answer: $0005 Which value(s) correspond to the key 04? Answer: $0003. I'm a little confused on the differences in number formating, but I'm assuming that they are interchangable. At any rate, I'm probably missing something here, because this answer is too simple. :)
-
Seraphin wrote:
Simple example: [$0001][00] [$0002][01] [$0003][04] [$0004][01] [$0005][02] Recursion - check element and its connectors 1. 0001 - my for loop checks all connectors -> Result: 0002 and 0004 (because Key is 01).
Just so I understand, you're starting with a value of (00)01 and asking which keys have this value? The result in this case being $0002 and $0004?
Seraphin wrote:
2. now check the connectors for connectors (we have 0002 and 0004) 3. 0002 has 0005(key = 02) and so on .....
So having gotten the $0002 and $0004 keys, you are now interested in which keys have those two keys as values? This suggestion may be exactly what Christian suggested, but I would switch things around and use the values as keys and the keys as values. Each key would have an array of values. It would look like this: [00][$0001] [01][$0002][$0004] [04][$0003] [02][$0005] Asking the question again, which value(s) correspond to the 01 key? Answer: $0002 and $0004. Which value(s) correspond to the key 02? Answer: $0005 Which value(s) correspond to the key 04? Answer: $0003. I'm a little confused on the differences in number formating, but I'm assuming that they are interchangable. At any rate, I'm probably missing something here, because this answer is too simple. :)
Hi Leslie, Just so I understand, you're starting with a value of (00)01 and asking which keys have this value? The result in this case being $0002 and $0004? Yes. Christian suggestion leads into overhead within the recursion. It's impossible. Try to make a recursion with 800 items, and you need about 10 min to loop through. Yes, good idea ... but really time consuming (overhead) The problem: Give me all connectors and subconnectors for current item. Lets draw better example: $1 [0] $2 [1] $3 [1] $4 [2] Result: a) $1 - $2 - $3 and b) $1 - $3 for the first line a) search connectors for $1 - found $2 and $3 then loop through founded subconnectors $2 and $3 $2 has $4 as connector $3 has no further connectors next element in main loop is §2 $2 - $4 .... $4 has no more connectors
-
Hi Leslie, Just so I understand, you're starting with a value of (00)01 and asking which keys have this value? The result in this case being $0002 and $0004? Yes. Christian suggestion leads into overhead within the recursion. It's impossible. Try to make a recursion with 800 items, and you need about 10 min to loop through. Yes, good idea ... but really time consuming (overhead) The problem: Give me all connectors and subconnectors for current item. Lets draw better example: $1 [0] $2 [1] $3 [1] $4 [2] Result: a) $1 - $2 - $3 and b) $1 - $3 for the first line a) search connectors for $1 - found $2 and $3 then loop through founded subconnectors $2 and $3 $2 has $4 as connector $3 has no further connectors next element in main loop is §2 $2 - $4 .... $4 has no more connectors
Ok, I'm still mulling this over, but would it help if the values were sorted? Say you have this: $1 [0] $2 [1] $3 [2] $4 [1] $5 [2] Then you sort them by values: $1 [0] $2 [1] $4 [1] $3 [2] $5 [2] What this buys you is that as soon as you encounter a value that doesn't equal the value you are currently searching with, you can stop the search for that value. And maybe even continue the search from that point for subconnectors. Say you are searching with value [1]. You find the connectors $2 and $4. Then you encounter value [2]. You know at that point that you've found all of the connectors for [1]. However, did [1] have a connection to $2? Yes. So since you are already at [2], you can begin the search for $2's subconnectors from right where you are. Same goes for $4, which was also a connector for [1]. Does this help?
-
Ok, I'm still mulling this over, but would it help if the values were sorted? Say you have this: $1 [0] $2 [1] $3 [2] $4 [1] $5 [2] Then you sort them by values: $1 [0] $2 [1] $4 [1] $3 [2] $5 [2] What this buys you is that as soon as you encounter a value that doesn't equal the value you are currently searching with, you can stop the search for that value. And maybe even continue the search from that point for subconnectors. Say you are searching with value [1]. You find the connectors $2 and $4. Then you encounter value [2]. You know at that point that you've found all of the connectors for [1]. However, did [1] have a connection to $2? Yes. So since you are already at [2], you can begin the search for $2's subconnectors from right where you are. Same goes for $4, which was also a connector for [1]. Does this help?