Help with effective algorithm

[Tamir Khason]

I have parent-child hashtable with more then 900K items and I have to build
all pathes for this. E.G
Key ParentKey
1 0
2 1
3 2
4 8
5 3
6 1
7 3
8 7
To build:
0-1-2-3-5
0-1-6
0-1-2-3-7-8-9-4
This is just example.

I tried 5 different algorithms, but noting gave me good performance.
Please assist


--
What dot.NET? Just ask:
"Please, www.dotNET.us !"

[Picho]

Tamir,

out of cuiriosity,
why do you use a Hashtable to hold all the data in the first place?
why not go on the old safe tree structure?
maybe each node will hold a HashTable to the child nodes?
it might not be so memory-effective but performance might be good
as i see it, you have to itterate or search or query the main hashtable for
each path.

just a thought/question.

Picho
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message
news:%2***************@TK2MSFTNGP12.phx.gbl...

I have parent-child hashtable with more then 900K items and I have to build
all pathes for this. E.G
Key ParentKey
1 0
2 1
3 2
4 8
5 3
6 1
7 3
8 7
To build:
0-1-2-3-5
0-1-6
0-1-2-3-7-8-9-4
This is just example.

I tried 5 different algorithms, but noting gave me good performance.
Please assist


--
What dot.NET? Just ask:
"Please, www.dotNET.us !"

[Tamir Khason]

Picha, thank you for reply

why do you use a Hashtable to hold all the data in the first place? The data I recieve in input is two hashtables from selialized source first
is ID/Value information
the second is Parent/Child relation, where Child and Parent are IDs from
first hashtable
why not go on the old safe tree structure? It makes sense if trees are small. We are speaking about at least 900K items
with complicated relationships, thus the parsing of even just creation of
TreeView will take a while
maybe each node will hold a HashTable to the child nodes? Not nessesery, 'cos it might be Child-Of-Child structures

--
Tamir
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message
news:%2***************@TK2MSFTNGP12.phx.gbl...

I have parent-child hashtable with more then 900K items and I have to
build all pathes for this. E.G
Key ParentKey
1 0
2 1
3 2
4 8
5 3
6 1
7 3
8 7
To build:
0-1-2-3-5
0-1-6
0-1-2-3-7-8-9-4
This is just example.

I tried 5 different algorithms, but noting gave me good performance.
Please assist


--
What dot.NET? Just ask:
"Please, www.dotNET.us !"

[Picho]

this is getting more a question than helping thread but anyway,

thinking outloud, seems to me it can go only two ways (as allways...)
either you have a data structure that supports your need (object graph->Tree
structure of some sort)
or you have a flat and fast data structure that is supported by a fast graph
rendering algorithm.

on the first option, you have a long construction time and a large memory
consumption.
on the other option, you have a "skinny" memory consumption, but a longer
construction time for each request.

seems to me, analyticly speaking, that it narrows down to one question (for
me at least):
how often do you query for these graphs/paths?
if its often, I would take the first approach, since all the paths are
visible and constructed,
if not... well I will not.

but : this is a question, not an answer. I am trying to learn something here
too. I am ignorant when it comes to performance and memory usage.
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message
news:eC*************@tk2msftngp13.phx.gbl...

Picha, thank you for reply

why do you use a Hashtable to hold all the data in the first place?

The data I recieve in input is two hashtables from selialized source first
is ID/Value information
the second is Parent/Child relation, where Child and Parent are IDs from
first hashtable

why not go on the old safe tree structure?

It makes sense if trees are small. We are speaking about at least 900K
items with complicated relationships, thus the parsing of even just
creation of TreeView will take a while

maybe each node will hold a HashTable to the child nodes?

Not nessesery, 'cos it might be Child-Of-Child structures

--
Tamir

"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message
news:%2***************@TK2MSFTNGP12.phx.gbl...

I have parent-child hashtable with more then 900K items and I have to
build all pathes for this. E.G
Key ParentKey
1 0
2 1
3 2
4 8
5 3
6 1
7 3
8 7
To build:
0-1-2-3-5
0-1-6
0-1-2-3-7-8-9-4
This is just example.

I tried 5 different algorithms, but noting gave me good performance.
Please assist


--
What dot.NET? Just ask:
"Please, www.dotNET.us !"

[Roni]

hi,

i posted today an article which is waitung for approving. The article is
about sorting algorithms. As far as it's proved search about "Algorithms
and Sorting".

best regards,
roni schuetz

*** Sent via Developersdex http://www.developersdex.com ***

[Tamir Khason]

ok, following answers:
The "line" structures quered very often, the rebuild procedure less in use,
however it will be rather greed procedure

"Picho" <SP********@telhai.ac.il> wrote in message
news:%2****************@TK2MSFTNGP14.phx.gbl...

this is getting more a question than helping thread but anyway,

thinking outloud, seems to me it can go only two ways (as allways...)
either you have a data structure that supports your need (object
graph->Tree structure of some sort)
or you have a flat and fast data structure that is supported by a fast
graph rendering algorithm.

on the first option, you have a long construction time and a large memory
consumption.
on the other option, you have a "skinny" memory consumption, but a longer
construction time for each request.

seems to me, analyticly speaking, that it narrows down to one question
(for me at least):
how often do you query for these graphs/paths?
if its often, I would take the first approach, since all the paths are
visible and constructed,
if not... well I will not.

but : this is a question, not an answer. I am trying to learn something
here too. I am ignorant when it comes to performance and memory usage.
"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message
news:eC*************@tk2msftngp13.phx.gbl...

Picha, thank you for reply

why do you use a Hashtable to hold all the data in the first place?

The data I recieve in input is two hashtables from selialized source
first is ID/Value information
the second is Parent/Child relation, where Child and Parent are IDs from
first hashtable

why not go on the old safe tree structure?

It makes sense if trees are small. We are speaking about at least 900K
items with complicated relationships, thus the parsing of even just
creation of TreeView will take a while

maybe each node will hold a HashTable to the child nodes?

Not nessesery, 'cos it might be Child-Of-Child structures

--
Tamir

"Tamir Khason" <ta**********@tcon-NOSPAM.co.il> wrote in message
news:%2***************@TK2MSFTNGP12.phx.gbl...
I have parent-child hashtable with more then 900K items and I have to
build all pathes for this. E.G
Key ParentKey
1 0
2 1
3 2
4 8
5 3
6 1
7 3
8 7
To build:
0-1-2-3-5
0-1-6
0-1-2-3-7-8-9-4
This is just example.

I tried 5 different algorithms, but noting gave me good performance.
Please assist


--
What dot.NET? Just ask:
"Please, www.dotNET.us !"

[Tamir Khason]

Where you posted it?
"Roni" <rs*@v-1.ch> wrote in message
news:ug**************@tk2msftngp13.phx.gbl...

hi,

i posted today an article which is waitung for approving. The article is
about sorting algorithms. As far as it's proved search about "Algorithms
and Sorting".

best regards,
roni schuetz

*** Sent via Developersdex http://www.developersdex.com ***